洛谷3379

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn=500010,inf=1e9; 5 int n,m,x,y,root,tot,dep[maxn],son[maxn],size[maxn],fa[maxn],top[maxn],last[maxn]; 6 struct edge{
    int to,pre;}e[maxn<<1]; 7 inline void read(int &k){ 8     k=0; int f=1; char c=getchar(); 9     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();10     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();11     k*=f;12 }13 void add(int x,int y){e[++tot].to=y; e[tot].pre=last[x]; last[x]=tot;}14 void dfs1(int x){15     size[x]=1; dep[x]=dep[fa[x]]+1;16     for (int i=last[x],to;i;i=e[i].pre)17     if ((to=e[i].to)!=fa[x]){18         fa[to]=x; dfs1(to);19         size[x]+=size[to];20         if (size[to]>size[son[x]]) son[x]=to;21     }22 }23 void dfs2(int x,int tp){24     top[x]=tp;25     if (son[x]) dfs2(son[x],tp);26     for (int i=last[x],to;i;i=e[i].pre)27     if ((to=e[i].to)!=fa[x]&&to!=son[x]) dfs2(to,to);28 }29 int lca(int x,int y){30     int f1=top[x],f2=top[y];31     while(f1!=f2){32         if (dep[f1]