链接
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;
}
}
}