dsu on tree板子题。这个trick保证均摊O(nlogn)的复杂度，要求资瓷O(1)将一个元素插入集合，清空集合时每个元素O(1)删除。（当然log的话就变成log^2了）
具体的，每次先遍历轻儿子的子树，暴力求得所需信息，每遍历完一棵轻子树都将其信息清空。然后遍历重子树，暴力求得所需信息，保留信息，再重新遍历轻子树将信息合并，最后加上根本身得到原子树的信息。
复杂度证明考虑每个点的信息被统计的次数，显然这只与其到根的路径上轻边条数有关，于是复杂度O(nlogn)。
#include#include #include #include #include #include using namespace std;#define ll long long#define N 100010 char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],p[N],fa[N],size[N],son[N],cnt[N],mx,t;ll ans[N],cur;struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void make(int k){ size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { fa[edge[i].to]=k; make(edge[i].to); size[k]+=size[edge[i].to]; if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to; }}void update(int x,int op){ cnt[x]+=op; if (op==1) { if (cnt[x]>mx) mx=cnt[x],cur=0; if (cnt[x]>=mx) cur+=x; } else mx=cur=0;}void add(int k,int op){ update(a[k],op); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) add(edge[i].to,op);}void dfs(int k){ for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs(edge[i].to),add(edge[i].to,-1); if (son[k]) dfs(son[k]); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) add(edge[i].to,1); update(a[k],1);ans[k]=cur;}int main(){#ifndef ONLINE_JUDGE freopen("600E.in","r",stdin); freopen("600E.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i