https://www.luogu.org/problemnew/show/P5290
神tm一道蓝题，我考试的时候都在想啥...
考虑一条链，显然你是把两个链分别的最大值放在一起，次大值放在一起，等等
那么如果有多个链呢？你就把第一个链和第二个链按上面的操作，得到的新的结果再和第三个链合并...
正确性挺显然的...qwq
复杂度O(nlog^2n)
#include#include #include #include #include using namespace std;#define O(x) cout << #x << " " << x << endl;#define B cout << "breakpoint" << endl;inline int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op;}typedef long long ll;const int maxn = 2e5 + 5;struct node{ int to,next,cost;}e[maxn << 1];int fir[maxn],alloc;void adde(int u,int v){ e[++alloc].next = fir[u]; fir[u] = alloc; e[alloc].to = v; swap(u,v); e[++alloc].next = fir[u]; fir[u] = alloc; e[alloc].to = v;}int a[maxn];int id[maxn],cnt,tp[maxn];priority_queue q[maxn];void dfs(int u,int fa){ //O(u); id[u] = ++cnt; for(int i = fir[u];i;i = e[i].next) { int v = e[i].to; if(v == fa) continue; dfs(v,u); if(q[id[u]].size() < q[id[v]].size()) swap(id[u],id[v]); int tot = q[id[v]].size(); for(int i = 1;i <= tot;i++) { tp[i] = max(q[id[u]].top(),q[id[v]].top()); q[id[u]].pop(),q[id[v]].pop(); } for(int i = 1;i <= tot;i++) q[id[u]].push(tp[i]); } q[id[u]].push(a[u]);}int main(){ int n = read(); for(int i = 1;i <= n;i++) a[i] = read(); for(int i = 2;i <= n;i++) { int f = read(); adde(f,i);} dfs(1,0); ll ans = 0; while(q[id[1]].size()) ans += q[id[1]].top(),q[id[1]].pop(); printf("%lld",ans);}