[十二省联考2019][贪心][启发式合并]春节十二响
题面
https://www.luogu.org/problemnew/show/P5290
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题解
最大的数a1所在的集合,会在它的每个祖先的所有其他儿子（即不包含a1本身的子树）中选出一个最大的数加入当前集合，证明过程同50pts的证法。同理，未选过数中第二大的数也会按照同样的方式，将剩下数中的某些数选进自己的集合。
以此类推。
这是什么？实际上是一个堆合并的过程，想象一下，每个数把其他数选进自己集合的操作，相当于直接把这个数的贡献从答案中扣除，若我们维护一个堆合并的过程，堆中记录当前节点及其子树中包含的权值，则在向上传递的过程中，该点的堆中权值从大到小，和它兄弟节点的堆的对应排名的权值，对于每个排名，只能留下一个权值，即堆的合并，本质上就是用大数消掉小数贡献的过程，只不过对于每个集合同时做而已。
考试上想到了60分的贪心，但我居然没写链的15分 就差每个子树一起贪心再每次把小堆合并到大堆上启发式合并就是正解了。。。 回头一看正解 真tm傻逼
时间复杂度O(nlogn)
发下来的solution以及楼上的题解中都有提到，认为它是log2,但是请注意，这道题和传统的启发式合并不一样，因为它并没有“合并”进去，
而是把小的那部分“贴”上去后直接把小的“丢掉了”，每个点只会被遍历一次，而每弹出一个点是log的，所以总时间复杂度是O(nlogn)。
这样做不就相当于是一个长链剖分吗?因为你每个节点堆的大小一定等于他到子树内最远点的距离，所以复杂度证明可以直接参考长链剖分
每个子树一起贪心是一个重要的技巧
1 #include<cstdio>
2 #include<algorithm>
3 #include<queue>
4 using namespace std; 5 const int N=2*1e5+15; 6 int n,v[N]; 7 int num,last[N],nxt[N],ver[N]; 8 inline void add(int x,int y) {nxt[++num]=last[x]; last[x]=num; ver[num]=y;} 9
10 inline int read() 11 {int re=0; char ch=getchar(); 12 while(!('0'<=ch && ch<='9')) ch=getchar(); 13 while('0'<=ch && ch<='9') {re=re*10+ch-'0',ch=getchar();} 14 return re; 15 } 16 int hao[N],t[N]; long long ans; 17 priority_queue<int> q[N]; 18 inline int merge(int x,int y) 19 {if(q[x].size()<q[y].size()) swap(x,y); 20
21 int sz=0; 22 while(!q[y].empty()) 23 {t[++sz]=max(q[x].top(),q[y].top()); 24 q[x].pop(); q[y].pop(); 25 } 26 for(int i=1;i<=sz;i++) q[x].push(t[i]); 27 return x; 28 } 29
30 int dfs(int x) 31 {hao[x]=x; 32 for(int i=last[x];i;i=nxt[i]) 33 {int y=ver[i]; 34 hao[x]=merge(hao[x],dfs(y)); 35 } 36 q[hao[x]].push(v[x]); 37 return hao[x]; 38 } 39 int main() 40 {n=read(); 41 for(int i=1;i<=n;i++) v[i]=read(); 42 for(int i=2;i<=n;i++) add(read(),i); 43
44 dfs(1); 45 while(!q[hao[1]].empty()) 46 {ans=ans+1ll*q[hao[1]].top(); q[hao[1]].pop();} 47
48 printf("%lld",ans); 49 return 0; 50 }
更多精彩
