Codeforces 600E 線段樹合并

題意：問你最多每一個子樹當中，出現次數最多的顔色的編号之和。

解：線段樹合并

#include <bits/stdc++.h>
#define  en '\n'
#define Swt  signed main
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn=1e5+10;
const int maxm=(1e5+10)*67;
int rd(){int tem;scanf("%d",&tem);return tem;}
 
int a[maxn];
int ls[maxm],rs[maxm],rt[maxn];
ll  ans[maxm],sm[maxm];
ll tot,n,que[maxn];
int dfn;
struct node{
int v,nxt;
}edge[maxn<<1];
int head[maxn];
int cnt=0;
void add(int x,int y){
edge[++cnt]=(node){y,head[x]};head[x]=cnt;
}
void up(int x){
    int lson=ls[x],rson=rs[x];
    if(sm[lson]==sm[rson]){
        sm[x]=sm[lson];
        ans[x]=ans[lson]+ans[rson];
    }
    else if(sm[lson]>sm[rson]){
        sm[x]=sm[lson];
        ans[x]=ans[lson];
    }
    else {
        sm[x]=sm[rson];
        ans[x]=ans[rson];
    }    return ;
}
int merge(int x,int y,int l,int r){
    if(!x or !y)return x+y;
    if(l==r){
        sm[x]+=sm[y];ans[x]=l;return x;
    }
    int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    up(x);
    return x;
}
void update(int &x,int l,int r,int pos){
    if(!x)x=++tot;
    if(l==r){sm[x]+=1;ans[x]=l;return ;}
    int mid=(l+r)>>1;
    if(pos<=mid)update(ls[x],l,mid,pos);
    else update(rs[x],mid+1,r,pos);
    up(x);
}
void dfs(int x,int fa){
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].v;
        if(y==fa)continue;
        dfs(y,x);
        rt[x]=merge(rt[x],rt[y],1,maxn-1);
    }
    update(rt[x],1,maxn-1,a[x]);
    que[rt[x]]=ans[rt[x]];
}
Swt(){
    #ifdef local
    freopen("input2.txt","r",stdin);
    #endif // local
    #define pb push_back
    cin>>n;tot=n;
    for(int i=1;i<=n;i++){a[i]=rd();rt[i]=i;}
    for(int i=1;i<n;i++){
        int x=rd(),y=rd();
        add(x,y),add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        cout<<que[i]<<' ';
    }cout<<en;
    return 0;
}