对于一个询问$x$,可以枚举答案$mid$,

将所有大于$mid$的路径填入,如果经过$x$的路径数等于填入路径数,则说明不存在一条路径不经过$x$而$>mid$,因此可以缩小答案的范围,反之亦然成立。

有意思的是求经过$x$的路径数,

首先考虑什么样的路径会经过$x$。

其一头势必经过$x$子树(含$x$)中某一个点,换言之,只有$x$子树中的点可能对当前询问产生贡献。

另一头势必在$x$子树外(含$x$)某一点,换言之,要减去在子树内的不经过$x$的路径数。

因此可以进行差分,每添加一条路径$(x,y)$,$x,y$处$+1$,$lca(x,y),fa(lca(x,y))$处$-1$。

需要时统计$x$子树权之和就是经过$x$的路径数。

整体二分处理一下就就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int siz[N],son[N],fa[N],dep[N];
void dfs1(int x)
{
    siz[x]=1;son[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if((y=a[k].y)==fa[x])continue;
        dep[y]=dep[x]+1;fa[y]=x;
        dfs1(y);
        siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
    }
}
int top[N],dfn[N],yss[N],cnt;
void dfs2(int x,int tp)
{
    top[x]=tp;dfn[x]=++cnt;yss[cnt]=x;
    if(son[x])dfs2(son[x],tp);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=son[x]&&y!=fa[x])dfs2(y,y);
}
inline int lca(int x,int y)
{
    while(top[x]!=top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]>dep[y]?y:x;
}
struct node
{
    int x,y,f,d,op;
    node(int x=0,int y=0,int f=0,int d=0,int op=0):x(x),y(y),f(f),d(d),op(op){}
}s[M],s1[M],s2[M];
int c[N],n,m;
inline void add(int x,int d){for(;x&&x<=n;x+=x&-x)c[x]+=d;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
void modify(int x,int y,int f,int d)//有点难理解,但这样差分是对未来点i,统计其子树权值和时会用到 
{
    add(dfn[x],d); 
    add(dfn[y],d);
    add(dfn[f],-d);
    add(dfn[fa[f]],-d);
}
int query(int x)
{
    return ask(dfn[x]+siz[x]-1)-ask(dfn[x]-1);
}
int ans[M];
void div(int l,int r,int L,int R)
{
    if(L==R)
    {
        for(int i=l;i<=r;i++)
            if(s[i].op)ans[s[i].op]=L;
        return ;    
    }
    int mid=L+R>>1;
    int l1=1,r1=0,l2=1,r2=0,sum=0;
    for(int i=l;i<=r;i++)
    {
        if(!s[i].op)
        {
            if(abs(s[i].d)>mid)
            {
                if(s[i].d>0)modify(s[i].x,s[i].y,s[i].f,1),++sum;
                else modify(s[i].x,s[i].y,s[i].f,-1),--sum;
                s2[++r2]=s[i];    
            }
            else s1[++r1]=s[i];
        }
        else
        {
            int ss=query(s[i].x);//求子树权值和,若>0,即说明有路径经过。
            if(ss==sum)s1[++r1]=s[i];
            else s2[++r2]=s[i]; 
        }
    }
    for(int i=1;i<=r1;i++)s[l+i-1]=s1[i];
    for(int i=1;i<=r2;i++)s[l+r1+i-1]=s2[i];
    for(int i=1;i<=r2;i++)
        if(!s2[i].op)
        {
            if(s2[i].d>0)modify(s2[i].x,s2[i].y,s2[i].f,-1);
            else modify(s2[i].x,s2[i].y,s2[i].f,1);
        }
    if(l1<=r1)div(l,l+r1-1,L,mid);
    if(l2<=r2)div(l+r1,r,mid+1,R);
}
int main()
{
    qr(n),qr(m);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    dfs1(1);dfs2(1,1);int qs=0;
    for(int i=1;i<=m;i++)
    {
        int type,x,y,d,t;qr(type);
        if(!type)
        {
            qr(x),qr(y),qr(d);
            s[i]=node(x,y,lca(x,y),d,0);
        }
        else if(type==1)qr(t),s[i]=s[t],s[i].d*=-1;
        else qr(x),s[i]=node(x,0,0,0,++qs);
    }
    div(1,m,0,(int)1e9);
    for(int i=1;i<=qs;i++)
        qw(ans[i]?ans[i]:-1),puts("");
    return 0;
}