例题：给出一棵树，求出每个节点的子树中出现次数最多的颜色的编号和

这个东西的时间复杂度竟然是nlogn的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int c[maxn],cnt[maxn],si[maxn],son[maxn],hson;
int n,tot=0,maxx;
ll sum=0,ans[maxn];

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int fa)
{
    int max_son=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>max_son) max_son=si[y],son[x]=y;
    }
}

void in(int x,int fa,int val)
{
    cnt[c[x]]+=val;
    if(cnt[c[x]]>maxx) maxx=cnt[c[x]],sum=c[x];
    else if(cnt[c[x]]==maxx) sum=sum+(ll)c[x];
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa||y==hson) continue;
        in(y,x,val);
    }
}

void dfs2(int x,int fa,int flag)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa||y==son[x]) continue;
        dfs2(y,x,0);
    }
    if(son[x])
    {
        dfs2(son[x],x,1);
        hson=son[x];
    }
    in(x,fa,1);
    hson=0;
    ans[x]=sum;
    if(!flag) in(x,fa,-1),sum=0,maxx=0;
}

int main(void)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    return 0;
}