链接
m<2000
建虚树后暴力
维护虚树中两点间的实际点的个数 模拟即可
巨丑的代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define yes puts("YES")
#define no puts("NO")
#define err puts("-1")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 5e5 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y)
{
    LL ans=1;
    x%=mod;
    while(y)
    {
        if(y&1)
            ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
LL inv(LL x)
{
    return qp(x,mod-2);
}

//head
int lgN,n,m,op[maxn],dfn[maxn],b[maxn],u[maxn],v[maxn],k[maxn],dep[maxn],tot;
int fa[maxn][30];
VI G[maxn],fake[maxn];
void dfs(int u,int f)
{
    dep[u]=dep[f]+1;
    fa[u][0]=f;
    dfn[u]=++tot;
    for(int i=1; i<=lgN; i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:G[u])
        if(v!=f)
        {
            dfs(v,u);
        }
}
int anc[maxn],dp[maxn];
void dfs1(int u,int f)
{
    anc[u]=f;
    dp[u]=dp[f]+1;
    for(int v:fake[u])
    {
        dfs1(v,u);
    }
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=lgN; i>=0; i--)
    {
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    }
    if(x==y)
        return x;
    for(int i=lgN; i>=0; i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int top,stk[maxn];
void append(int u)
{
    if(top<=1)
    {
        stk[++top]=u;
        return;
    }
    int lca=LCA(u,stk[top]);
    if(lca==stk[top])
    {
        stk[++top]=u;
        return;
    }
    while(top>1&&dfn[lca]<=dfn[stk[top-1]])
    {
        fake[stk[top-1]].pb(stk[top]);
        top--;
    }
    if(lca!=stk[top])
    {
        fake[lca].pb(stk[top]);
        stk[top]=lca;
    }
    stk[++top]=u;
}
bool cmp(int a,int b)
{
    return dfn[a]<dfn[b];
}
int _,cnt;
LL w[maxn],a[maxn],num[maxn];
void upd(int i)
{
    int x=u[i],y=v[i];
    if(op[i]<=3)
    {
        while(x!=y)
        {
            if(dp[x]<dp[y])
                swap(x,y);
            ///x->fa[x]

            if(op[i]==1)
            {
                w[x]+=k[i];
                a[x]+=k[i];
            }
            else if(op[i]==2)
            {
                w[x]^=k[i];
                a[x]^=k[i];
            }
            else
            {
                if(w[x]>=k[i]) w[x]-=k[i];
                if(a[x]>=k[i]) a[x]-=k[i];
            }
            x=anc[x];
        }
        if(op[i]==1)
        {
            a[x]+=k[i];
        }
        else if(op[i]==2)
        {
            a[x]^=k[i];
        }
        else
        {if(a[x]>=k[i])
            a[x]-=k[i];
        }
        return ;
    }
    LL ans=0;
    if(op[i]==4)
    {
        while(x!=y)
        {
            if(dp[x]<dp[y])
                swap(x,y);
            ans+=w[x]*(dep[x]-dep[anc[x]]-1)+a[x];
            x=anc[x];
        }
        ans+=a[x];
        printf("%lld\n",ans);
        return ;
    }

    if(op[i]==5)
    {
        while(x!=y)
        {
            if(dp[x]<dp[y])
                swap(x,y);
            if((dep[x]-dep[anc[x]]-1)&1)
                ans^=w[x];
            ans^=a[x];
            x=anc[x];
        }
        ans^=a[x];
        printf("%lld\n",ans);
        return ;
    }

    if(op[i]==6)
    {
        LL mx=-inf,mn=inf;
        while(x!=y)
        {
            if(dp[x]<dp[y])
                swap(x,y);

            if((dep[x]-dep[anc[x]]-1))
                mx=max(mx,w[x]),mn=min(mn,w[x]);
            mx=max(mx,a[x]),mn=min(mn,a[x]);

            x=anc[x];
        }
        mx=max(mx,a[x]);
        mn=min(mn,a[x]);
        printf("%lld\n",mx-mn);
        return ;
    }

    if(op[i]==7)
    {
        ans=inf;
        while(x!=y)
        {
            if(dp[x]<dp[y])
                swap(x,y);
            if((dep[x]-dep[anc[x]]-1))
                ans=min(ans,abs(w[x]-k[i]));
            ans=min(ans,abs(a[x]-k[i]));
            x=anc[x];
        }
        ans=min(ans,abs(a[x]-k[i]));
        printf("%lld\n",ans);
        return ;
    }
}
int main()
{
    for(scanf("%d",&_); _; _--)
    {
        scanf("%d%d",&n,&m);
        cnt=tot=0;
        lgN=(int)log(n)/log(2)+1;
        for(int i=1; i<n; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].pb(v);
            G[v].pb(u);
        }
        dfs(1,0);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&op[i],&u[i],&v[i]);
            b[++cnt]=u[i];
            b[++cnt]=v[i];
            if(op[i]<=3||op[i]==7)
                scanf("%d",&k[i]);
            else
                k[i]=0;
        }
        sort(b+1,b+1+cnt);
        cnt=unique(b+1,b+1+cnt)-b-1;
        sort(b+1,b+1+cnt,cmp);
        top=0;
        stk[++top]=1;
        for(int i=1; i<=cnt; i++)
            if(b[i]!=1)
                append(b[i]);
        while(top>1)
            fake[stk[top-1]].pb(stk[top]),top--;
        dfs1(1,0);
        for(int i=1; i<=m; i++)
        {
            upd(i);
        }
        for(int i=1; i<=n; i++)
            G[i].clear(),fake[i].clear(),w[i]=a[i]=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<=lgN; j++)
                fa[i][j]=0;
        }
    }
}