首页 > 代码库 > Codeforces 600E. Lomsat gelral(Dsu on tree学习)
Codeforces 600E. Lomsat gelral(Dsu on tree学习)
题目链接：http://codeforces.com/problemset/problem/600/E
n个点的有根树，以1为根，每个点有一种颜色。我们称一种颜色占领了一个子树当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。
我们都知道可以$BST$启发式合并从而完美${O(nlogn^{2})}$，这太丑陋了。
那么$Dsu~~on~~tree$是在干啥呢？
找出树中每一个节点的重儿子，统计答案的时候优先进入每一个点的所有轻儿子，之后再进入重儿子，目的是保留重儿子所在子树的信息。
处理完当前点的所有儿子的子树之后开始处理自己。
先统计以当前点为根的子树不经过重儿子的所有点的影响${O(size[x]-size[hson[x]])}$
如果这个点是轻儿子则需要暴力删除这棵子树所带来的影响${O(size[x])}$，这也正是先进入轻儿子的原因，可以保留重儿子的信息。
考虑复杂度为什么正确：
不妨想想一个点被反复计算了多少次？是不是${O(这个点到根的轻边条树)}$，这个东西是${O(logn)}$级别的。
最终复杂度:${O(nlogn)}$
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 30010010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,hson[maxn],size[maxn],ans[maxn],c[maxn],cnt[maxn],sum,mx,S;13 vector<llg>a[maxn];14 15 inline llg getint()16 {17 llg w=0,q=0; char c=getchar();18 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 19 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;20 }21 22 void init()23 {24 llg x,y;25 cin>>n;26 for (llg i=1;i<=n;i++) c[i]=getint();27 for (llg i=1;i<n;i++)28 {29 x=getint(),y=getint();30 a[x].push_back(y),a[y].push_back(x);31 }32 }33 34 void find_hson(llg x,llg fa)35 {36 size[x]=1;37 llg w=a[x].size(),v;38 for (llg i=0;i<w;i++)39 {40 v=a[x][i];41 if (v==fa) continue;42 find_hson(v,x);43 size[x]+=size[v];44 if (size[v]>size[hson[x]]) hson[x]=v;45 }46 }47 48 void calc(llg x,llg fa,llg val)49 {50 cnt[c[x]]+=val;51 if (cnt[c[x]]>mx) sum=c[x],mx=cnt[c[x]];52 else53 {54 if (cnt[c[x]]==mx) sum+=c[x];55 }56 llg w=a[x].size(),v;57 for (llg i=0;i<w;i++)58 {59 v=a[x][i];60 if (v==fa || v==S) continue;61 calc(v,x,val);62 }63 }64 65 void dfs(llg x,llg fa,llg t)66 {67 llg w=a[x].size(),v;68 for (llg i=0;i<w;i++)69 {70 v=a[x][i];71 if (v==fa || v==hson[x]) continue;72 dfs(v,x,-1);73 }74 if (hson[x]) dfs(hson[x],x,1),S=hson[x];75 calc(x,fa,1); S=0;76 ans[x]=sum;77 if (t==-1) calc(x,fa,-1),mx=sum=0;78 }79 80 int main()81 {82 yyj("tree");83 init();84 find_hson(1,0);85 dfs(1,0,1);86 for (llg i=1;i<=n;i++) printf("%lld ",ans[i]);87 return 0;88 }
Codeforces 600E. Lomsat gelral(Dsu on tree学习)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。