题目链接：https://www.luogu.com.cn/problem/CF600E

思路： 先处理出那些点是重儿子  然后对于每一个结点 先处理完轻儿子 再暴力清除掉

然后再处理重儿子 处理之后不用清除，回到根结点 再让处理根节点，让根节点带上重儿子的信息再跑一遍轻儿子的信息得到答案

暴力的话 每个点跑2n次 是n^2 只跑轻儿子的话 则时间复杂度 o（nlogn）

  1 #include<bits/stdc++.h>
  2 #define ll long long
  3 #define pb push_back
  4 using namespace std;
  5 const int maxn=1e5+10;
  6 const int mod=1e9+7;
  7 vector<int>E[maxn];
  8 int n,son[maxn],cnt[maxn];
  9 int c[maxn],num[maxn],vis[maxn];
 10 ll ans[maxn];
 11 
 12 void get(int u,int fa)
 13 {
 14     cnt[u]=1;
 15     int p=0,max1=0;
 16     for(auto &v:E[u])
 17     {
 18         if(v==fa)
 19             continue;
 20         get(v,u);
 21         if(cnt[v]>max1)
 22         {
 23             max1=cnt[v];
 24             p=v;
 25         }
 26         cnt[u]+=cnt[v];
 27     }
 28     vis[p]=1;
 29 }
 30 ll sum=0,max1=0;
 31 
 32 void init(int u,int fa)
 33 {
 34     num[c[u]]--;
 35     for(auto &v:E[u])
 36     {
 37         if(v==fa)
 38             continue;
 39         init(v,u);
 40     }
 41 }
 42 
 43 void solve(int u,int fa,int p)
 44 {
 45     num[c[u]]++;
 46     if(num[c[u]]>max1)
 47     {
 48         max1=num[c[u]];
 49         sum=c[u];
 50     }
 51     else if(num[c[u]]==max1)
 52     {
 53         sum+=c[u];
 54     }
 55     for(auto &v:E[u])
 56     {
 57         if(v==fa||v==p)//不能把重儿子也跑了
 58             continue;
 59         solve(v,u,p);
 60     }
 61 }
 62 
 63 void dfs(int u,int fa)
 64 {
 65     int p=0;
 66     for(auto &v:E[u])
 67     {
 68         if(v==fa)
 69             continue;
 70         if(!vis[v])
 71         {
 72             dfs(v,u);
 73             init(v,u);
 74             max1=0,sum=0;
 75         }
 76         else
 77             p=v;
 78     }
 79     if(p) dfs(p,u);
 80     solve(u,fa,p);
 81     ans[u]=sum;
 82 
 83 }
 84 
 85 
 86 int main()
 87 {
 88     ios::sync_with_stdio(0);
 89     cin.tie(0);
 90     cin>>n;
 91     for(int i=1;i<=n;i++)
 92     {
 93         cin>>c[i];
 94     }
 95     for(int i=1;i<n;i++)
 96     {
 97         int x,y;
 98         cin>>x>>y;
 99         E[x].pb(y);
100         E[y].pb(x);
101     }
102     get(1,0);
103     dfs(1,0);
104     for(int i=1;i<=n;i++)
105     {
106         if(i!=1)
107             cout<<" ";
108         cout<<ans[i];
109     }
110     cout<<'\n';
111 
112 
113 }

View Code