题目：
看博客：
还是不太明白复杂度...
代码如下：
#include#include #include #include using namespace std;typedef long long ll;int const xn=1e5+5;int n,c[xn],hd[xn],ct,to[xn<<1],nxt[xn<<1],cnt[xn],siz[xn],son[xn],mx,big;ll ans[xn],sum;void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}int rd(){ int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return f?ret:-ret;}void dfs(int x,int fa){ siz[x]=1; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; dfs(u,x); siz[x]+=siz[u]; if(siz[u]>siz[son[x]])son[x]=u; }}void add(int x,int fa,int v){ cnt[c[x]]+=v; if(cnt[c[x]]>mx)sum=c[x],mx=cnt[c[x]]; else if(cnt[c[x]]==mx)sum+=c[x]; for(int i=hd[x],u;i;i=nxt[i]) if((u=to[i])!=fa&&u!=big)add(u,x,v);}void dfs2(int x,int fa,int keep){ for(int i=hd[x],u;i;i=nxt[i]) if((u=to[i])!=fa&&u!=son[x])dfs2(u,x,0); if(son[x])dfs2(son[x],x,1),big=son[x]; add(x,fa,1); big=0; ans[x]=sum; if(!keep)add(x,fa,-1),mx=sum=0;//=0!}int main(){ n=rd(); for(int i=1;i<=n;i++)c[i]=rd(); for(int i=1,x,y;i