题目
6s时限，T(T<=5)组样例，每次给出n(n<=5e5)个点的树，初始时，每个点的点权w都是0，
m(m<=2e3)次操作，操作分7种，
1 u v k，u到v的路径所有点点权都加k(k<=1e5)
2 u v k，u到v的路径所有点点权都异或k(k<=1e8)
3 u v k，u到v的路径所有点点权都减k，如果点权小于k，忽略该操作
4 u v，询问u到v的路径点权和
5 u v，询问u到v的路径点权异或和
6 u v，询问u到v的路径点权中的最大值减最小值
7 u v k，询问u到v的路径点权中与k最接近的数与k的绝对值之差(k<=1e8)
思路来源
https://www.cnblogs.com/LiuRunky/p/Virtual_Tree.html 常规建虚树，维护边权
https://blog.csdn.net/cat_pikapikapi/article/details/90673849 树形dp式建树
题解
建虚树，把关键点和lca建到虚树里，
lca和关键点之间有一些链，链上的点也需要缩成一个点，建在虚树里，其实就是树上离散化
其中蓝点是询问的点，绿点是虚树保留的lca，
橙点是原来这条链上需要参与计算的点缩的点，
根据实现方式不同，
第一种代码采用类似树形dp的方式建虚树，
第二种代码常规建虚树，把一条链维护的信息放在了关键点和lca之间的边上来维护，
更简单无脑一点，即把橙点当成蓝绿点之间的边
建完虚树之后，就暴力维护7种操作即可，
M个询问，最多出现2M个点，包括lca后4M个点，
则第一种建树方法，虚树点不会超过16000，第二种不会超过8000
代码1（树型dp建树）
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const ll INF=1e17;
const int N=5e5+10,M=2e3+10;
ll w[N];
int t,n,m,x,y,dep[N],par[N];
int chain[N],now[N];//chain:缩出来的链长 now:当前点子树里离当前点最近的关键点
bool sub[N],is[N];//sub:子树里是否有关键点 is:是否是关键点
vector<int>e[N];
int op[M],u[M],v[M],k[M];
void dfs(int u,int fa){
int sum=0,pos;
chain[u]=1;
now[u]=u;
for(int v:e[u]){
if(v==fa)continue;
dep[v]=dep[u]+1;
dfs(v,u);
if(!sub[v])continue;//防止改变pos
sub[u]|=sub[v];
sum+=sub[v];
pos=now[v];
}
if(!sub[u])return;
if(!is[u] && sum==1){//只有一个子树有关键点
if(is[pos]){//是关键点
par[pos]=u;
}
else{//是链缩出来的点
now[u]=pos;
chain[pos]++;
}
return;
}
is[u]=1;//两个子树的lca 是关键点
for(int v:e[u]){
if(v==fa || !sub[v])continue;
par[now[v]]=u;
}
}
ll cal(int op,int x,int y,int v){
ll mx=-INF,mn=INF,res=0;
while(1){
if(dep[x]<dep[y])swap(x,y);
switch(op){
case 1:w[x]+=v;break;
case 2:w[x]^=v;break;
case 3:if(w[x]>=v)w[x]-=v;break;
case 4:res+=w[x]*chain[x];break;
case 5:if(chain[x]&1)res^=w[x];break;
case 6:mx=max(mx,w[x]);mn=min(mn,w[x]);res=mx-mn;break;
case 7:mn=min(mn,abs(w[x]-v));res=mn;break;
}
if(x==y)break;
x=par[x];
}
return res;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
e[i].clear();
sub[i]=is[i]=w[i]=dep[i]=0;
}
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
e[x].pb(y);e[y].pb(x);
}
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op[i],&u[i],&v[i]);
if(op[i]<4 || op[i]>6)scanf("%d",&k[i]);
is[u[i]]=is[v[i]]=1;
sub[u[i]]=sub[v[i]]=1;
}
dfs(1,-1);
for(int i=1;i<=m;++i){
ll ans=cal(op[i],u[i],v[i],k[i]);
if(op[i]>3)printf("%lld\n",ans);
}
}
return 0;
}
代码2（常规建树）
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const ll INF=1e17;
const int N=500010,M=2e3+10,LG=20;
int t,n,m,x,y;
int op[M],u[M],v[M],k[M];
vector<int>e[N];
int head[N],cnt,nex[N],to[N];//虚树
ll w[N+4*M];//2M个点的询问 4M个点的虚树
int stk[N],top;//虚树栈
int dep[N],f[N][LG+1];//lca
bool key[N];//关键点
void add(int u,int v){//par[u]=v
nex[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=LG;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){
x=f[x][i];
}
}
if(x==y)return x;
for(int i=LG;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i],y=f[y][i];
}
}
return f[x][0];
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<=LG;i++){
f[u][i]=f[f[u][i-1]][i-1];
}
if(key[u]){
int p=lca(u,stk[top]);
if(p!=stk[top]){
while(dep[stk[top-1]]>dep[p]){
add(stk[top],stk[top-1]);
top--;
}
add(stk[top],p);
top--;
if(stk[top]!=p){
stk[++top]=p;
}
}
stk[++top]=u;
}
for(int v:e[u]){
if(v==fa)continue;
dfs(v,u);
}
}
void build(){//以0为虚根
top=1;
dfs(1,0);
for(int i=top;i>=1;i--){
add(stk[i],stk[i-1]);
}
}
ll cal(int op,int x,int y,int v){
ll mx=-INF,mn=INF,res=0;
int fa;
while(1){
if(dep[x]<dep[y])swap(x,y);
for(int i=head[x];i;i=nex[i]){
fa=to[i];
switch(op){//点
case 1:w[x]+=v;break;
case 2:w[x]^=v;break;
case 3:if(w[x]>=v)w[x]-=v;break;
case 4:res+=w[x];break;
case 5:res^=w[x];break;
case 6:mx=max(mx,w[x]);mn=min(mn,w[x]);res=mx-mn;break;
case 7:mn=min(mn,abs(w[x]-v));res=mn;break;
}
if(x!=y){//边
int num=dep[x]-dep[fa]-1;
if(num){
switch(op){
case 1:w[n+i]+=v;break;
case 2:w[n+i]^=v;break;
case 3:if(w[n+i]>=v)w[n+i]-=v;break;
case 4:res+=w[n+i]*num;break;
case 5:if(num&1)res^=w[n+i];break;
case 6:mx=max(mx,w[n+i]);mn=min(mn,w[n+i]);res=mx-mn;break;
case 7:mn=min(mn,abs(w[n+i]-v));res=mn;break;
}
}
}
}
if(x==y)break;
x=fa;
}
return res;
}
void init(){
cnt=0;
memset(w,0,sizeof w);
for(int i=1;i<=n;++i){
e[i].clear();
key[i]=head[i]=0;
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
e[x].pb(y);e[y].pb(x);
}
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op[i],&u[i],&v[i]);
if(op[i]<4 || op[i]>6)scanf("%d",&k[i]);
key[u[i]]=key[v[i]]=1;
}
build();
for(int i=1;i<=m;++i){
ll ans=cal(op[i],u[i],v[i],k[i]);
if(op[i]>3)printf("%lld\n",ans);
}
}
return 0;
}
