【CF600E】Lomsat gelral（dsu on tree）

题意：n个点的有根树，以1为根，每个点有一种颜色。我们称一种颜色占领了一个子树当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。

n<=1e5,a[i]<=n

思路：参考资料：http://codeforces.com/blog/entry/44351

https://www.cnblogs.com/zzqsblog/p/6146916.html

https://blog.csdn.net/QAQ__QAQ/article/details/53455462

dsu on tree模板

用类似树剖的方法轻重链剖分，轻儿子暴力维护影响，重儿子保留影响

只支持子树查询不支持修改

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 typedef pair<ll,int>P;
 11 #define N  100010
 12 #define M  200010
 13 #define fi first
 14 #define se second
 15 #define MP make_pair
 16 #define pi acos(-1)
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 20 #define lowbit(x) x&(-x)
 21 #define Rand (rand()*(1<<16)+rand())
 22 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 23 #define ls p<<1
 24 #define rs p<<1|1
 25 
 26 const ll MOD=1e9+7,inv2=(MOD+1)/2;
 27       double eps=1e-6;
 28       ll INF=1ll<<62;
 29       ll inf=5e13;
 30       int dx[4]={-1,1,0,0};
 31       int dy[4]={0,0,-1,1};
 32 
 33 int head[N],vet[M],nxt[M],tot;
 34 int son[N],skip[N],a[N],c[N],size[N],mx;
 35 ll ans[N],sum;
 36 
 37 int read()
 38 {
 39    int v=0,f=1;
 40    char c=getchar();
 41    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 42    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 43    return v*f;
 44 }
 45 
 46 void add(int a,int b)
 47 {
 48     nxt[++tot]=head[a];
 49     vet[tot]=b;
 50     head[a]=tot;
 51 }
 52 
 53 void dfs1(int u,int fa)
 54 {
 55     size[u]=1;
 56     int e=head[u];
 57     while(e)
 58     {
 59         int v=vet[e];
 60         if(v!=fa)
 61         {
 62             dfs1(v,u);
 63             size[u]+=size[v];
 64             if(size[v]>size[son[u]]) son[u]=v;
 65         }
 66         e=nxt[e];
 67     }
 68 }
 69 
 70 void solve(int u,int fa,int op)
 71 {
 72     c[a[u]]+=op;
 73     if(op>0&&c[a[u]]>=mx)
 74     {
 75         if(c[a[u]]>mx) sum=0,mx=c[a[u]];
 76         sum+=a[u];
 77     }
 78     int e=head[u];
 79     while(e)
 80     {
 81         int v=vet[e];
 82         if(v!=fa&&!skip[v]) solve(v,u,op);
 83         e=nxt[e];
 84     }
 85 }
 86 
 87 void dfs2(int u,int fa,int op)
 88 {
 89     int e=head[u];
 90     while(e)
 91     {
 92         int v=vet[e];
 93         if(v!=fa&&v!=son[u]) dfs2(v,u,0);
 94         e=nxt[e];
 95     }
 96     if(son[u])
 97     {
 98         dfs2(son[u],u,1);
 99         skip[son[u]]=1;
100     }
101     solve(u,fa,1);
102     ans[u]=sum;
103     if(son[u]) skip[son[u]]=0;
104     if(!op)
105     {
106         solve(u,fa,-1);
107         sum=mx=0;
108     }
109 }
110 
111 int main()
112 {
113     int n=read();
114     rep(i,1,n) a[i]=read();
115     tot=0;
116     rep(i,1,n-1)
117     {
118         int x=read(),y=read();
119         add(x,y);
120         add(y,x);
121     }
122     dfs1(1,0);
123     sum=mx=0;
124     dfs2(1,0,0);
125     rep(i,1,n) printf("%I64d ",ans[i]);
126     return 0;
127 }