• 难点在于读懂题面.
• \(dsu\ on\ tree\), 注意深度是相对深度,记录答案时减去节点本身深度.时间复杂度为 \(O(nlogn)\) .
• 本题还可以使用达到 \(O(n)\) 的时间复杂度.

#include
    
     using namespace std;#define ll long long#define mp make_pair#define pii pair
     
      inline int read(){    int x=0;    bool pos=1;    char ch=getchar();    for(;!isdigit(ch);ch=getchar())        if(ch=='-')            pos=0;    for(;isdigit(ch);ch=getchar())        x=x*10+ch-'0';    return pos?x:-x;}const int MAXN=1e6+10;int n;int ecnt=0,head[MAXN],nx[MAXN<<1],to[MAXN<<1];inline void addedge(int u,int v){    ++ecnt;    nx[ecnt]=head[u];    to[ecnt]=v;    head[u]=ecnt;    swap(u,v);    ++ecnt;    nx[ecnt]=head[u];    to[ecnt]=v;    head[u]=ecnt;}int mxson[MAXN],siz[MAXN],dep[MAXN];int cnt[MAXN],mxcnt,pos,bigson;void getsiz(int u,int fa){    siz[u]=1;    dep[u]=dep[fa]+1;    for(int i=head[u];i;i=nx[i])        {            int v=to[i];            if(v!=fa)                {                    getsiz(v,u);                    if(siz[v]>siz[mxson[u]])                        mxson[u]=v;                    siz[u]+=siz[v];                }        }}int ans[MAXN];void add(int u,int fa,int val){    int s=(cnt[dep[u]]+=val);    if(s>mxcnt)        mxcnt=s,pos=dep[u];    else if(s==mxcnt)        pos=min(pos,dep[u]);    for(int i=head[u];i;i=nx[i])        {            int v=to[i];            if(v!=fa && v!=bigson)                add(v,u,val);        }}void dfs(int u,int fa,bool keep){    for(int i=head[u];i;i=nx[i])        {            int v=to[i];            if(v!=fa && v!=mxson[u])                dfs(v,u,false);        }    if(mxson[u])        dfs(mxson[u],u,true),bigson=mxson[u];    add(u,fa,1);    ans[u]=pos-dep[u];    bigson=0;    if(keep==false)        {            add(u,fa,-1);            mxcnt=0;        }}int main(){    int n=read();    for(int i=1;i