传送门
是一种套路的变式
如果不考虑祖孙关系的限制,临项扰动一下就可以得到 \(\frac{a}{b}\) 小的优先的策略
但现在有些点有一些前置点要考虑
先有一个结论:按比值小的贪心选点,若选到一个点时其父节点还没选,则在选中其父节点后一定会立刻选这个点
然后就可以缩点,把这些一定连续选的点缩在一起
对多个连续点临项扰动后发现缩过的点的 \(a\) 和 \(b\) 就是其组成点的 \(a, b\) 之和
于是可以并查集+堆实现
a.splice(a.end(), b)
可以把b接到a的后面#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 300010 #define ll long long #define fir first #define sec second #define make make_pair #define pb push_back //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n; int head[N], size; ll a[N], b[N]; struct edge{int to, next;}e[N<<1]; inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;} namespace force{ ll ans; int p[N], fa[N], back[N]; void solve() { for (int i=2; i<=n; ++i) fa[i]=read(); for (int i=1; i<=n; ++i) a[i]=read(), b[i]=read(); for (int i=1; i<=n; ++i) p[i]=i; do { ll sum=0; for (int i=1; i<=n; ++i) back[p[i]]=i; for (int i=2; i<=n; ++i) if (back[fa[i]]>back[i]) goto jump; for (int i=1; i<=n; ++i) { for (int j=i+1; j<=n; ++j) { sum+=b[p[i]]*a[p[j]]; } } ans=max(ans, sum); jump: ; } while (next_permutation(p+1, p+n+1)); printf("%lld\n", ans); exit(0); } } namespace task1{ priority_queue<pair<double, int>> q; int sta[N], top; ll suf[N]; void solve() { memset(head, -1, sizeof(head)); for (int i=2; i<=n; ++i) add(read(), i); for (int i=1; i<=n; ++i) a[i]=read(), b[i]=read(); q.push(make(-1.0*a[1]/b[1], 1)); pair<double, int> u; while (q.size()) { u=q.top(); q.pop(); sta[++top]=u.sec; for (int i=head[u.sec],v; ~i; i=e[i].next) { v = e[i].to; q.push(make(-1.0*a[v]/b[v], v)); } } ll ans=0; for (int i=n; i; --i) suf[i]=suf[i+1]+a[sta[i]]; for (int i=1; i<=n; ++i) ans+=b[sta[i]]*suf[i+1]; // cout<<"sta: "; for (int i=1; i<=top; ++i) cout<<sta[i]<<' '; cout<<endl; printf("%lld\n", ans); exit(0); } } namespace task2{ int p[N], fa[N]; ll ans; bool vis[N]; void check() { ll sum=0; for (int i=1; i<=n; ++i) { for (int j=i+1; j<=n; ++j) { sum+=b[p[i]]*a[p[j]]; } } ans=max(ans, sum); } void dfs(int u) { if (u>n) {check(); return ;} for (int i=1; i<=n; ++i) if (!vis[i] && vis[fa[i]]) { vis[i]=1; p[u]=i; dfs(u+1); vis[i]=0; } } void solve() { for (int i=2; i<=n; ++i) fa[i]=read(); for (int i=1; i<=n; ++i) a[i]=read(), b[i]=read(); vis[1]=1; p[1]=1; dfs(2); printf("%lld\n", ans); exit(0); } } namespace task{ priority_queue<pair<double, int>> q; list<int> inc[N]; int fa[N], f[N], sta[N], stop, siz[N], top[N]; ll a[N], b[N], a2[N], b2[N], suf[N]; bool vis[N]; inline int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);} inline void uni(int x, int y) { // cout<<"uni: "<<x<<' '<<y<<endl; int ttop=top[x]; // for (auto it:inc[y]) inc[x].pb(it); inc[x].splice(inc[x].end(), inc[y]); siz[x]+=siz[y]; fa[y]=x; a[x]=(a[x]+a[y]); b[x]=(b[x]+b[y]); top[x]=ttop; } void solve() { for (int i=2; i<=n; ++i) top[i]=f[i]=read(); for (int i=1; i<=n; ++i) fa[i]=i, inc[i].emplace_back(i), siz[i]=1; for (int i=1; i<=n; ++i) a2[i]=a[i]=read(), b2[i]=b[i]=read(); sta[++stop]=1; vis[1]=1; for (int i=2; i<=n; ++i) q.push(make(-1.0*a[i]/b[i], i)); pair<double, int> u; while (q.size()) { u=q.top(); q.pop(); // cout<<"u: "<<u.fir<<' '<<u.sec<<endl; if (u.sec!=fa[u.sec]) continue; // u.sec=find(u.sec); if (vis[find(u.sec)]) continue; if (vis[find(top[u.sec])]) {vis[u.sec]=1; for (auto it:inc[u.sec]) sta[++stop]=it; continue;} // cout<<"top: "<<top[u.sec]<<endl; uni(find(top[u.sec]), u.sec); u.sec=find(u.sec); q.push(make(-1.0*a[u.sec]/b[u.sec], u.sec)); } ll ans=0; for (int i=n; i; --i) suf[i]=suf[i+1]+a2[sta[i]]; for (int i=1; i<=n; ++i) ans+=b2[sta[i]]*suf[i+1]; // cout<<"sta: "; for (int i=1; i<=stop; ++i) cout<<sta[i]<<' '; cout<<endl; printf("%lld\n", ans); exit(0); } } signed main() { freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); n=read(); // if (n<=20) task2::solve(); // else task1::solve(); task::solve(); return 0; }