Problem：
给定一个无向图，n个点，n-1条边，每个点有一个初始状态（标记/未标记），q个操作，每次操作修改一个点的状态（状态取反）/询问所有标记点到x->y的简单路径的距离之和。
Solution：
首先找到x->y的简单路径，然后求标记节点u到这条链的距离（u到LCA的距离减去u到LCA的路径与链的重合部分的长度），最后进行路径求和。
对于重合路径，对u->root的路径进行+1标记，然后每次查询链上路径和。
对于u->LCA的距离，有 dis（u，LCA）= dis（u，root）+ dis（LCA，root）- 2 * dis（lca（u，LCA））。
Code:
#include<bits/stdc++.h>
using namespace std; #define ll long long const int N=2e5+7; int n,m,a[N]; int dep[N];//节点深度 int f[N];//父节点 int son[N];//最大子节点 int sz[N];//子树大小 int top[N];//树链剖分后节点所在链的首节点 int num[N];//遍历次序 int LCA; int dfn=0;//记录遍历点个数 ll cnt=0;//标记点个数 ll siz[N];//子树中标记点个数 ll vis[N];//x->y简单路径不经过该节点时，节点子树中标记点接收信息在该路径上的能量消耗 ll pw[N];//连接父节点的边的边权 ll sw[N];//连接最大子节点的边的边权 ll tp; struct tree{ ll w; ll sum; ll lazy; }t[N<<2]; int head[N],tot=0; struct node{ int nxt,to,val; }e[N<<1]; //快读 inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } //建图 inline void add(int x,int y,int z){ e[++tot].nxt=head[x]; e[tot].to=y; e[tot].val=z; head[x]=tot; return ; } //预处理深度、父节点、子节点、标记、边权 inline void dfs1(int x,int fa){ f[x]=fa; dep[x]=dep[fa]+1; siz[x]=a[x]; sz[x]=1; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(y!=fa){ dfs1(y,x); siz[x]+=siz[y]; sz[x]+=sz[y]; if(sz[son[x]]<sz[y]){ son[x]=y; sw[x]=e[i].val; } } } return ; } //预处理 inline void dfs2(int x,int tpx,ll ww){ ++dfn;//遍历个数 num[x]=dfn;//x节点是第num[x]个遍历到的 vis[dfn]=ww*siz[x];//第dfn个遍历到的节点的子树中标记点个数*该节点到父节点的路径长度 pw[dfn]=ww;//第dfn个遍历到的节点到父节点的路径长度 top[x]=tpx;//x节点所在链的链首节点 if(son[x]) dfs2(son[x],tpx,sw[x]);//递归重链 for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; int w=e[i].val; if(y!=son[x]&&y!=f[x]){ dfs2(y,y,w);//递归轻链 } } return ; } //递归建树 inline void build(int l,int r,int x){ if(l==r){ t[x].sum=pw[l]; t[x].w=vis[l]; return; } int mid=(l+r)>>1; build(l,mid,x<<1);//左子树 build(mid+1,r,x<<1|1);//右子树 t[x].w=t[x<<1].w+t[x<<1|1].w; t[x].sum=t[x<<1].sum+t[x<<1|1].sum; return ; } //更新 inline void pushdown(int x){ if(t[x].lazy){ t[x<<1].lazy+=t[x].lazy; t[x<<1|1].lazy+=t[x].lazy; t[x<<1].w+=t[x<<1].sum*t[x].lazy; t[x<<1|1].w+=t[x<<1|1].sum*t[x].lazy; t[x].lazy=0; } return ; } inline void update(int l,int r,int p,int q,int x,ll y){ if(p<=l&&r<=q){ t[x].lazy+=y; t[x].w+=t[x].sum*y;
return; } int mid=l+r>>1; pushdown(x); if(p<=mid) update(l,mid,p,q,x<<1,y); if(q>mid) update(mid+1,r,p,q,x<<1|1,y); t[x].w=t[x<<1].w+t[x<<1|1].w; return ; } //修改点的状态 inline void updt(int x,int y){ int pp=a[y]?-1:1;//取反 while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); update(1,n,num[top[x]],num[x],1,pp); x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); update(1,n,num[x],num[y],1,pp); return ; } inline ll qu1(int l,int r,int p,int q,int x){ if(p>q) return 0; if(p<=l&&r<=q) return t[x].w; int mid=l+r>>1; ll ans=0; pushdown(x); if(p<=mid) ans=qu1(l,mid,p,q,x<<1); if(q>mid) ans+=qu1(mid+1,r,p,q,x<<1|1); return ans; } inline ll qu2(int l,int r,int p,int q,int x){ if(p>q) return 0; if(p<=l&&r<=q) return t[x].sum; int mid=l+r>>1; ll ans=0; pushdown(x); if(p<=mid) ans=qu2(l,mid,p,q,x<<1); if(q>mid) ans+=qu2(mid+1,r,p,q,x<<1|1); return ans; } inline ll qu4(int x,int y){ ll ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=qu2(1,n,num[top[x]],num[x],1); x=f[top[x]];
} if(dep[x]>dep[y]) swap(x,y); ans+=qu2(1,n,num[x]+1,num[y],1); return ans; } inline ll qu3(int x,int y){ ll ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=qu1(1,n,num[top[x]],num[x],1); x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=qu1(1,n,num[x]+1,num[y],1); LCA=x; return ans; } inline ll find(int x,int y){ tp=qu3(x,y); int w=LCA; return t[1].w-tp-2ll*qu3(1,w)+cnt*qu4(1,w); } int main(){ n=read(); m=read(); tp=read(); for(int i=1;i<n;++i){ int u,v,w; u=read(); v=read(); w=read(); add(u,v,w); add(v,u,w); } for(int i=1;i<=n;++i) a[i]=read(); dfs1(1,0); dfs2(1,1,0); build(1,n,1); cnt=siz[1]; for(int i=1;i<=m;++i){ int opt=read(); int u=read(); if(opt==1){ cnt=cnt+(a[u]?-1:1);//更新cnt updt(1,u); a[u]=!a[u];//取反 } else{ int v=read(); printf("%lld\n",find(u,v)); } } return 0; }