用到的知识

线段树/树状数组+树链剖分+整体二分
没学过的建议先去学了再回来做这道题

解题思路

题目要求的是不经过x的所有路径中最大的路径，那么我们可以考虑使用二分：
对于每条v大于mid的路径，将路径上的点+1（路径上的点对应线段树的点，这部分使用树链剖分+线段树/树状数组实现），并统计路径总数，然后查询x点的值，如果x点的值与路径总数相等，即证明所有大于mid的路径都经过x，此时需要减小mid，重复操作，否则，则存在不经过x的路径，增大mid
我们发现，这个操作可以同时针对所有询问，于是，使用整体二分
复杂度O(m logm logn logn) 为什么是三个log？ logm是对离散化后的答案区间二分（一共m种重要度），第一层logn是树链剖分路径修改，第二层logn 是线段树/树状数组查询(一共n个点）

用到的算法

树状数组(可以用线段树）

树状数组用于区间+1和-1（请求结束可视为区间-1）,查询x点的值
我们把树状数组视为差分数组，两个单点更新即为区间更新，查询前缀和即为查询单点的值
代码实现：

//树状数组 
#define lowbit(i) i&-i
int tree[mx];//树状数组的差分数组
void change_point(int i,int k){//更新差分数组 
    while(i<=n){
        tree[i]+=k;
        i+=lowbit(i);
    }
} 
int query(int i){//单点查询 
    int ans=0;
    while(i>0){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}
void change(int l,int r,int k){//区间更新 
    change_point(l,k);change_point(r+1,-k);
}

树链剖分

我们使用树链剖分来把一颗树变成一个区间，并使得在同一条重链上的点的编号连续
代码实现：

//树剖
int head[mx];
int num; 
struct Edge{
    int v,next;
}edge[mx<<1];
void addedge(int u,int v){//加一条单向边 
    edge[++num].v=v;
    edge[num].next=head[u];
    head[u]=num;
}
void add_edge(int u,int v){//加双向边 
    addedge(u,v);
    addedge(v,u);
}
int dfn[mx],deep[mx];//每个点的dfs序,深度 
int fa[mx],size[mx],son[mx];//每个点的父亲，子树大小，重儿子 
void dfs1(int u,int f){
    size[u]=1;
    int max_size=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==f)continue;
        fa[v]=u;
        deep[v]=deep[u]+1;
        dfs1(v,u);
        size[u]+=size[v];
        if(max_size<size[v]){
            max_size=size[v];
            son[u]=v; 
        } 
    }
} 
int T;//时间戳 
int top[mx];//重链顶端 
void dfs2(int u,int tp){
    dfn[u]=++T;
    top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(fa[u]!=v&&son[u]!=v)dfs2(v,v);
    }
}
void change_path(int u,int v,int k){//从u到v的路径上的点全部+k 
    while(top[u]!=top[v]){
        if(deep[top[u]]>deep[top[v]])swap(u,v);
        change(dfn[top[v]],dfn[v],k);
        v=fa[top[v]];
    }
    if(deep[u]<deep[v])swap(u,v);
    change(dfn[v],dfn[u],k);
}

整体二分

前面已经讲的比较详细了，这里直接放代码：

//整体二分 
struct Query{
    int type;//type==0:(a,b,t,v) type==1:del(t) type==2:x was broken
    int a,b,t,v;
    int k;//type==0:k=1 type==1:k=-1
    int x;
}q[mx],ql[mx],qr[mx];
bool Cmp(Query x,Query y){//按t升序 
    return x.t<y.t;
}
int cnt_a;//一共多少个v 
int a[mx];//原序列 
int b[mx];//离散化序列 
int O;//离散化后共多少个数 
void discretization(){//离散化 
    sort(a+1,a+1+cnt_a);
    b[++O]=a[1];
    for(int i=2;i<=cnt_a;++i)if(a[i]!=a[i-1])b[++O]=a[i];
}
int ans[mx];//每个询问的答案
void solve(int l,int r,int L,int R){//[l,r]为当前答案所在区间，[L,R]为当前处理问题区间
    if(l==r){
        for(int i=L;i<=R;++i)if(q[i].type==2)ans[q[i].t]=l;
        return;
    } 
    int cnt1=0,cnt2=0,mid=(l+r)>>1;//左右区间的操作数 
    int s=0;//当前共有多少个请求 
    for(int i=L;i<=R;++i){
        if(q[i].type==2){
            int sum=query(dfn[q[i].x]);//v比mid大并且经过x的请求有多少个
            if(sum==s)ql[++cnt1]=q[i];//比mid大的请求全部被断了，往小的找 
            else qr[++cnt2]=q[i];//有没被断的请求 
        }
        else{
            if(q[i].v>b[mid]){
                change_path(q[i].a,q[i].b,q[i].k);
                s+=q[i].k;
                qr[++cnt2]=q[i];
            }
            else ql[++cnt1]=q[i];
        }
    }
    for(int i=1;i<=cnt2;++i)if(qr[i].type!=2)change_path(qr[i].a,qr[i].b,-qr[i].k);//清空树状数组 
    for(int i=1;i<=cnt1;++i)q[L+i-1]=ql[i];
    for(int i=1;i<=cnt2;++i)q[L+cnt1+i-1]=qr[i];
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,cnt1+L,R);
} 

完整代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
const int mx=201010;
int n,m;
//树状数组 
#define lowbit(i) i&-i
int tree[mx];//树状数组的差分数组
void change_point(int i,int k){//更新差分数组 
    while(i<=n){
        tree[i]+=k;
        i+=lowbit(i);
    }
} 
int query(int i){//单点查询 
    int ans=0;
    while(i>0){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}
void change(int l,int r,int k){//区间更新 
    change_point(l,k);change_point(r+1,-k);
}
//树剖
int head[mx];
int num; 
struct Edge{
    int v,next;
}edge[mx<<1];
void addedge(int u,int v){//加一条单向边 
    edge[++num].v=v;
    edge[num].next=head[u];
    head[u]=num;
}
void add_edge(int u,int v){//加双向边 
    addedge(u,v);
    addedge(v,u);
}
int dfn[mx],deep[mx];//每个点的dfs序,深度 
int fa[mx],size[mx],son[mx];//每个点的父亲，子树大小，重儿子 
void dfs1(int u,int f){
    size[u]=1;
    int max_size=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==f)continue;
        fa[v]=u;
        deep[v]=deep[u]+1;
        dfs1(v,u);
        size[u]+=size[v];
        if(max_size<size[v]){
            max_size=size[v];
            son[u]=v; 
        } 
    }
} 
int T;//时间戳 
int top[mx];//重链顶端 
void dfs2(int u,int tp){
    dfn[u]=++T;
    top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(fa[u]!=v&&son[u]!=v)dfs2(v,v);
    }
}
void change_path(int u,int v,int k){//从u到v的路径上的点全部+k 
    while(top[u]!=top[v]){
        if(deep[top[u]]>deep[top[v]])swap(u,v);
        change(dfn[top[v]],dfn[v],k);
        v=fa[top[v]];
    }
    if(deep[u]<deep[v])swap(u,v);
    change(dfn[v],dfn[u],k);
}
//整体二分 
struct Query{
    int type;//type==0:(a,b,t,v) type==1:del(t) type==2:x was broken
    int a,b,t,v;
    int k;//type==0:k=1 type==1:k=-1
    int x;
}q[mx],ql[mx],qr[mx];
bool Cmp(Query x,Query y){//按t升序 
    return x.t<y.t;
}
int cnt_a;//一共多少个v 
int a[mx];//原序列 
int b[mx];//离散化序列 
int O;//离散化后共多少个数 
void discretization(){//离散化 
    sort(a+1,a+1+cnt_a);
    b[++O]=a[1];
    for(int i=2;i<=cnt_a;++i)if(a[i]!=a[i-1])b[++O]=a[i];
}
int ans[mx];//每个询问的答案
void solve(int l,int r,int L,int R){//[l,r]为当前答案所在区间，[L,R]为当前处理问题区间
    if(l==r){
        for(int i=L;i<=R;++i)if(q[i].type==2)ans[q[i].t]=l;
        return;
    } 
    int cnt1=0,cnt2=0,mid=(l+r)>>1;//左右区间的操作数 
    int s=0;//当前共有多少个请求 
    for(int i=L;i<=R;++i){
        if(q[i].type==2){
            int sum=query(dfn[q[i].x]);//v比mid大并且经过x的请求有多少个
            if(sum==s)ql[++cnt1]=q[i];//比mid大的请求全部被断了，往小的找 
            else qr[++cnt2]=q[i];//有没被断的请求 
        }
        else{
            if(q[i].v>b[mid]){
                change_path(q[i].a,q[i].b,q[i].k);
                s+=q[i].k;
                qr[++cnt2]=q[i];
            }
            else ql[++cnt1]=q[i];
        }
    }
    for(int i=1;i<=cnt2;++i)if(qr[i].type!=2)change_path(qr[i].a,qr[i].b,-qr[i].k);//清空树状数组 
    for(int i=1;i<=cnt1;++i)q[L+i-1]=ql[i];
    for(int i=1;i<=cnt2;++i)q[L+cnt1+i-1]=qr[i];
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,cnt1+L,R);
} 
int main(){
    n=Read(),m=Read();
    for(int i=1;i<n;++i){
        int u=Read(),v=Read();
        add_edge(u,v);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;++i){
        q[i].type=Read();
        if(q[i].type==0){
            q[i].a=Read();
            q[i].b=Read();
            a[++cnt_a]=q[i].v=Read();
            q[i].k=1;
        }
        if(q[i].type==1){
            int t=Read();
            q[i]=q[t];
            q[i].k=-1;
        }
        if(q[i].type==2){
            q[i].x=Read();
        }
        q[i].t=i;
    }
    discretization();
    solve(0,O,1,m);
    sort(q+1,q+1+m,Cmp);
    for(int i=1;i<=m;++i)if(q[i].type==2)printf("%d\n",ans[q[i].t]!=0?b[ans[q[i].t]]:-1);
    return 0;
} 

解释一下倒数第二行：如果ans==0，则证明对于任何mid>0，所有路径都会经过x，所以按题目要求，输出-1