这题就是每次维护一条链上的信息，如果普通暴力，那么复杂度会超，但是我们观察到m只有2e3，每次只有两个点，因此我们把所有可能操作的点以及他们的lca全部保留下来
新建成一棵虚树，就能维护所有的信息，并且所有的点不会超过8000，也就是说每次最多操作8e3的点，最多有2e3次的操作，所以相乘不会超时。
建立虚树就是通过dfs序排序后用栈来维护所需要的点。
注意的是，本题是对链上操作，所以有一些不在虚树上的点，例如两个关键点之间的所有点我们是没有建出来的，但是我们发现对于这些点，他们的权值一定是相等的。
因此我们将这些点缩成一个点来维护，根据树的性质，每个节点都有一个父亲，因此可以把他到父亲这条链上的点都用这个点+n这个位置来维护即可，这样就能做到唯一。
在暴力操作链的时候，需要往上跳，因此将儿子连到父亲这样跳起来会快一点
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; vector<int> num; int dfn[N],id[N],tot,idx; int h[N],ne[N],e[N],q[N]; int n,m,depth[N],times; int f[N][30],u[N],v[N],k[N],opt[N]; int valf[N],pid[N]; ll val[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void init(){ num.clear(); memset(h,-1,sizeof h); idx=0; tot=0; for(int i=1;i<N;i++){ k[i]=0; val[i]=0; pid[i]=0; valf[i]=0; } } void dfs(int u,int fa){ dfn[u]=++times; f[u][0]=fa; depth[u]=depth[fa]+1; int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; dfs(j,u); } } void pp(){ int i,j; for(i=1;i<=27;i++){ for(j=1;j<=n;j++){ f[j][i]=f[f[j][i-1]][i-1]; } } } bool cmp(int a,int b){ return dfn[a]<dfn[b]; } void addx(int a,int b){ valf[b]=a; pid[b]=++tot; } int lca(int a,int b){ if(depth[a]<depth[b]) swap(a,b); int i; for(i=27;i>=0;i--){ if(depth[f[a][i]]>=depth[b]){ a=f[a][i]; } } if(a==b) return a; for(i=27;i>=0;i--){ if(f[a][i]!=f[b][i]){ a=f[a][i]; b=f[b][i]; } } return f[a][0]; } void build(){ sort(num.begin(),num.end()); num.erase(unique(num.begin(),num.end()),num.end()); sort(num.begin(),num.end(),cmp); int tt=1; q[tt]=1; int i; for(i=0;i<(int)num.size();i++){ if(num[i]==1) continue; int p=lca(num[i],q[tt]); if(p!=q[tt]){ while(dfn[p]<dfn[q[tt-1]]){ addx(q[tt-1],q[tt]); tt--; } if(dfn[p]!=dfn[q[tt-1]]){ addx(p,q[tt]); q[tt]=p; } else{ addx(p,q[tt]); tt--; } } q[++tt]=num[i]; } for(i=1;i<tt;i++){ addx(q[i],q[i+1]); } } ll get(int x,int d,int choice){ if(choice==1){ return x+d; } if(choice==2){ return (x^d); } if(choice==3){ return (x>=d?x-d:x); } } void modify(int x,int y,int d,int choice){ int tmp[2]={x,y}; int p=lca(x,y); for(int i=0;i<2;i++){ int ans=tmp[i]; while(ans!=p){ val[ans]=get(val[ans],d,choice); val[n+pid[ans]]=get(val[n+pid[ans]],d,choice); //cout<<p<<" "<<valf[ans]<<endl; ans=valf[ans]; } } val[p]=get(val[p],d,choice); } ll sum,xorsum,maxv,minv,minabs; ll update(ll x,int d,int sz){ sum+=1ll*sz*x; xorsum=xorsum^(sz%2*x); maxv=max(maxv,x); minv=min(minv,x); minabs=min(minabs,abs(x-d)); } ll query(int x,int y,int d,int choice){ int tmp[2]={x,y}; int p=lca(x,y); sum=0,xorsum=0,maxv=0,minv=1<<30,minabs=1<<30; for(int i=0;i<2;i++){ int ans=tmp[i]; while(ans!=p){ int sz=depth[ans]-depth[valf[ans]]-1; update(val[ans],d,1); if(sz){ update(val[n+pid[ans]],d,sz); } ans=valf[ans]; } } update(val[p],d,1); if(choice==4){ return sum; } if(choice==5){ return xorsum; } if(choice==6){ return maxv-minv; } if(choice==7) return minabs; } int main(){ //ios::sync_with_stdio(false); int t; cin>>t; while(t--){ scanf("%d%d",&n,&m); init(); int i,j; for(i=1;i<n;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1,0); pp(); for(i=1;i<=m;i++){ scanf("%d%d%d",&opt[i],&u[i],&v[i]); num.push_back(u[i]); num.push_back(v[i]); if(opt[i]<=3||opt[i]==7){ scanf("%d",&k[i]); } } build(); for(i=1;i<=m;i++){ if(opt[i]<=3){ modify(u[i],v[i],k[i],opt[i]); } else{ printf("%lld ",query(u[i],v[i],k[i],opt[i])); } } } }