首页 > 代码库 > codeforces600E Lomsat gelral
codeforces600E Lomsat gelral
题面：codeforces600E
学习一下$dsu \ on \ tree$。。
这个东西可以处理很多无修改子树问题，复杂度通常为$O(nlogn)$。
主要操作是：我们先把整棵树链剖一下，然后每次先递归轻儿子，再递归重儿子。
对于每棵子树，我们暴力加入整棵子树的贡献。如果是重儿子的子树则另外处理：加入贡献时不考虑加重儿子所在的子树，而在消除贡献时也不消除重儿子的子树，直到它成为某个点的轻儿子的子树的一部分时再消除贡献。
复杂度：因为每个轻儿子最多被加入$O(logn)$次(递归轻儿子时$size$至少$/2$)，每条重链最多只会被加入$O(logn)$次，所以复杂度是$O(nlogn)$的。
说得有点玄学，还是看看代码吧。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define N (200010)15 #define il inline16 #define RG register17 #define ll long long18 19 using namespace std;20 21 struct edge{ int nt,to; }g[N<<1];22 23 int head[N],col[N],son[N],sz[N],c[N],n,num,Mx,flag;24 ll ans[N],Sum;25 26 il int gi(){27 RG int x=0,q=1; RG char ch=getchar();28 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();29 if (ch==‘-‘) q=-1,ch=getchar();30 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();31 return q*x;32 }33 34 il void insert(RG int from,RG int to){35 g[++num]=(edge){head[from],to},head[from]=num; return;36 }37 38 il void dfs1(RG int x,RG int p){39 sz[x]=1; RG int v;40 for (RG int i=head[x];i;i=g[i].nt){41 v=g[i].to; if (v==p) continue;42 dfs1(v,x),sz[x]+=sz[v];43 if (sz[son[x]]<=sz[v]) son[x]=v;44 }45 return;46 }47 48 il void add(RG int x,RG int p,RG int val){49 col[c[x]]+=val; RG int v;50 if (Mx<col[c[x]]) Mx=col[c[x]],Sum=c[x];51 else if (Mx==col[c[x]]) Sum+=c[x];52 for (RG int i=head[x];i;i=g[i].nt){53 v=g[i].to; if (v==p || v==flag) continue;54 add(v,x,val);55 }56 return;57 }58 59 il void dfs2(RG int x,RG int p,RG int fg){60 RG int v;61 for (RG int i=head[x];i;i=g[i].nt){62 v=g[i].to; if (v!=p && v!=son[x]) dfs2(v,x,1);63 }64 if (son[x]) dfs2(son[x],x,0),flag=son[x];65 add(x,p,1),flag=0,ans[x]=Sum;66 if (fg) add(x,p,-1),Mx=Sum=0; return;67 }68 69 int main(){70 #ifndef ONLINE_JUDGE71 freopen("600E.in","r",stdin);72 freopen("600E.out","w",stdout);73 #endif74 n=gi();75 for (RG int i=1;i<=n;++i) c[i]=gi();76 for (RG int i=1,u,v;i<n;++i)77 u=gi(),v=gi(),insert(u,v),insert(v,u);78 dfs1(1,0),dfs2(1,0,1);79 for (RG int i=1;i<=n;++i) printf("%I64d ",ans[i]);80 return 0;81 }
codeforces600E Lomsat gelral
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。