Description

一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和。

Input

第一行一个$n$。第二行$n$个数字是$c[i]$。后面$n-1$行给出树边。

Output

一行答案。

Sample Input1

4

1 2 3 4

1 2

2 3

2 4

Sample Output1

10 9 3 4

Sample Input2

15

1 2 3 1 2 3 3 1 1 3 2 2 1 2 3

1 2

1 3

1 4

1 14

1 15

2 5

2 6

2 7

3 8

3 9

3 10

4 11

4 12

4 13

Sample Output2

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

Solution

线段树合并模板题，但我竟然读错题了QAQ……

情况特殊所以$Merge$的时候要加上$l$，$r$。

没啥好说的看代码就能懂……

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (100009) 5 #define LL long long 6 using namespace std; 7  8 struct Sgt{
   int ls,rs,max; LL val;}Segt[N*50]; 9 struct Edge{
   int to,next;}edge[N<<1];10 int n,x,u,v,sgt_num,c[N],Root[N];11 int head[N],num_edge;12 13 void add(int u,int v)14 {15     edge[++num_edge].to=v;16     edge[num_edge].next=head[u];17     head[u]=num_edge;18 }19 20 void Pushup(int now)21 {22     int ls=Segt[now].ls, rs=Segt[now].rs;23     if (Segt[ls].max==Segt[rs].max)24     {25         Segt[now].max=Segt[ls].max;26         Segt[now].val=Segt[ls].val+Segt[rs].val;27     }28     else if (Segt[ls].max>Segt[rs].max)29     {30         Segt[now].max=Segt[ls].max;31         Segt[now].val=Segt[ls].val;32     }33     else34     {35         Segt[now].max=Segt[rs].max;36         Segt[now].val=Segt[rs].val;37     }38 }39 40 void Update(int &now,int l,int r,int v)41 {42     if (!now) now=++sgt_num;43     if (l==r)44     {45         Segt[now].max=1;46         Segt[now].val=v;47         return;48     }49     int mid=(l+r)>>1;50     if (v<=mid) Update(Segt[now].ls,l,mid,v);51     else Update(Segt[now].rs,mid+1,r,v);52     Pushup(now);53 }54 55 int Merge(int x,int y,int l,int r)56 {57     if (!x || !y) {
   return x|y;}58     int tmp=++sgt_num;59     if (l==r)60     {61         Segt[tmp].max=Segt[x].max+Segt[y].max;62         Segt[tmp].val=l; return tmp;63     }64     int mid=(l+r)>>1;65     Segt[tmp].ls=Merge(Segt[x].ls,Segt[y].ls,l,mid);66     Segt[tmp].rs=Merge(Segt[x].rs,Segt[y].rs,mid+1,r);67     Pushup(tmp); return tmp;68 }69 70 void DFS(int x,int fa)71 {72     for (int i=head[x]; i; i=edge[i].next)73         if (edge[i].to!=fa)74         {75             DFS(edge[i].to,x);76             Root[x]=Merge(Root[x],Root[edge[i].to],1,n);77         }78 }79 80 int main()81 {82     scanf("%d",&n);83     for (int i=1; i<=n; ++i)84     {85         scanf("%d",&c[i]);86         Update(Root[i],1,n,c[i]);87     }88     for (int i=1; i<=n-1; ++i)89     {90         scanf("%d%d",&u,&v);91         add(u,v); add(v,u);92     }93     DFS(1,0);94     for (int i=1; i<=n; ++i)95         printf("%lld ",Segt[Root[i]].val);96 }