[题解]:

 

#include
       
        #include
        
         #include
         
          using namespace std;const int N=1e5+5;struct edge{
     int v,next;}e[N<<1];int tot,head[N],cur[N];int n,m,top,st[N<<1];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void add(int x,int y){    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;}int dfs_cnt,dfn[N],end[N],pos[N];int fa[N],fat[N][20],dep[N];void dfs(){    memcpy(cur,head,sizeof head);    int x;st[++top]=1;dep[1]=1;    while(top){con:        x=st[top];        if(!dfn[x]) dfn[x]=++dfs_cnt;        for(int &i=cur[x];i;){            if(e[i].v==fa[x]){i=e[i].next;continue;}             fa[e[i].v]=x;            fat[e[i].v][0]=x;            dep[e[i].v]=dep[x]+1;            st[++top]=e[i].v;            i=e[i].next;            goto con;        }        end[x]=dfs_cnt; top--;    }    for(int i=1;i<=n;i++) pos[dfn[i]]=i;}const int M=N<<2;int mx[M],tag[M];#define lch k<<1#define rch k<<1|1void build(int k,int l,int r){    if(l==r){        mx[k]=dep[pos[l]];return ;    }    int mid=l+r>>1;    build(lch,l,mid);    build(rch,mid+1,r);    mx[k]=max(mx[lch],mx[rch]);}void pushdown(int k){    if(!tag[k]) return ;    mx[lch]+=tag[k];    mx[rch]+=tag[k];    tag[lch]+=tag[k];    tag[rch]+=tag[k];    tag[k]=0;}void plusx(int k,int l,int r,int x,int y,int val){    if(l==x&&r==y){        mx[k]+=val;        tag[k]+=val;        return ;    }    pushdown(k);    int mid=l+r>>1;    if(y<=mid) plusx(lch,l,mid,x,y,val);    else if(x>mid) plusx(rch,mid+1,r,x,y,val);    else plusx(lch,l,mid,x,mid,val),plusx(rch,mid+1,r,mid+1,y,val);    mx[k]=max(mx[lch],mx[rch]);}int ask(int k,int l,int r,int p){    if(l==r) return mx[k];    pushdown(k);    int mid=l+r>>1;    if(p<=mid) return ask(lch,l,mid,p);    else return ask(rch,mid+1,r,p);}int query(int k,int l,int r,int x,int y){    if(l==x&&r==y) return mx[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return query(lch,l,mid,x,y);    else if(x>mid) return query(rch,mid+1,r,x,y);    else return max(query(lch,l,mid,x,mid),query(rch,mid+1,r,mid+1,y));}int siz[N],ch[N][2];bool isroot(int x){    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void rotate(int x){    int y=fa[x],z=fa[y],l,r;    l=(ch[y][1]==x);r=l^1;    if(!isroot(y)) ch[z][ch[z][1]==y]=x;    fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;    ch[y][l]=ch[x][r];ch[x][r]=y;}void splay(int x){    while(!isroot(x)){        int y=fa[x],z=fa[y];        if(!isroot(y)){            if((ch[y][0]==x)^(ch[z][0]==y)) rotate(x);            else rotate(y);        }        rotate(x);    }}int findmin(int x){    if(!x) return 0;    for(;ch[x][0];x=ch[x][0]);    return x;}void access(int x){    for(int y=0,z;x;y=x,x=fa[x]){        splay(x);        z=findmin(ch[x][1]);        if(z) plusx(1,1,n,dfn[z],end[z],1);        if(fa[x]){            z=findmin(x);            plusx(1,1,n,dfn[z],end[z],-1);        }        ch[x][1]=y;    }}int lca(int a,int b){    if(dep[a]