题目大意
- 给出一个树，求出每个节点的子树中出现次数最多的颜色的编号和
题解
- 这是一道dsu on tree的模板题
- 那dsu on tree到底是个啥东西呢
-
dsu on tree是一种类似暴力的做法，用来解决一类树上询问的问题。一般有两种特征：①只有对子树询问 ②没有修改操作
dsu on tree运用了类似轻重链剖分把复杂度给降到O(nlogn)
算法流程：先dfs处理出每个父节点的重轻儿子，然后统计的时候，先递归处理每个轻儿子的贡献，同时消除递归产生的影响，然后递归重儿子，不消除递归的影响，再统计所有轻儿子对答案的影响，最后更新该节点的答案和删除所有轻儿子对答案的影响
我们来证明一下这个东东的复杂度，我们考虑一个点会被访问几次，发现只有两种情况，一种是暴力统计轻边的时候访问到，因为一个点到根的轻边数量不会多于logn条，所以次数＜logn；第二种是通过重边被访问到显然每个点只会被访问一次。综上所述，如果一个点所贡献的复杂度为O(1)的话，总复杂度为O(nlogn)
- 然后我们就可以发现用上面这个东西，可以很暴力的解决这个问题
代码
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <vector> 5 #define N 100010 6 #define ll long long 7 using namespace std; 8 int n,mx,Son,col[N],son[N],sz[N],cnt[N]; 9 ll sum,ans[N]; 10 vector<int>Q[N]; 11 int read() 12 { 13 char c=getchar(); int x=0,f=1; 14 while (c<'0'||c>'9') { if(c == '-') f=-1;c=getchar(); } 15 while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 16 return x*f; 17 } 18 void add(int x,int fa,int val) 19 { 20 cnt[col[x]]+=val; 21 if (cnt[col[x]]>mx) mx=cnt[col[x]],sum=col[x]; else if (cnt[col[x]]==mx) sum+=(ll)col[x]; 22 for (int i=0;i<Q[x].size();i++) if (Q[x][i]!=fa&&Q[x][i]!=Son) add(Q[x][i],x,val); 23 } 24 void dfs1(int x,int fa) 25 { 26 sz[x]=1; 27 for (int i=0;i<Q[x].size();i++) 28 if (Q[x][i]!=fa) 29 { 30 dfs1(Q[x][i],x),sz[x]+=sz[Q[x][i]]; 31 if (sz[Q[x][i]]>sz[son[x]]) son[x]=Q[x][i]; 32 } 33 } 34 void dfs2(int x,int fa,int op) 35 { 36 for (int i=0;i<Q[x].size();i++) if (Q[x][i]!=fa&&Q[x][i]!=son[x]) dfs2(Q[x][i],x,0); 37 if (son[x]) dfs2(son[x],x,1),Son=son[x]; 38 add(x,fa,1),Son=0,ans[x]=sum; 39 if (!op) add(x,fa,-1),sum=0,mx=0; 40 } 41 int main() 42 { 43 n=read(); 44 for (int i=1;i<=n;i++) col[i]=read(); 45 for (int i=1,x,y;i<n;i++) x=read(),y=read(),Q[x].push_back(y),Q[y].push_back(x); 46 dfs1(1,0),dfs2(1,0,0); 47 for (int i=1;i<=n;i++) printf("%lld ",ans[i]); 48 }