题意
1 u：把第 u 条边改成黑边。2 u：把第 u 条边改成白边。3 u v：若 u 号节点和 v 号节点间存在白边，输出 -1，否则输出 u 号节点和 v 号节点间的黑边数。分析
树链剖分板子题。
询问是看u到v节点的路径间是否存在白边，一个简单的技巧就是将白边记为1，黑边记为0。如果有一条链上的和>0，说明路径上存在白色的边。
要有记得要把点权下推到同一条边上深度更大的点（常用技巧）。
CODE:
#include<bits/stdc++.h> using namespace std; int n,m,opt,x,y,cnt,tot,u[100010],v[100010],h[100010],dad[100010],top[100010],dep[100010],size[100010],son[100010],id[100010],out; char c; struct Edge { int to,next; }e[200010]; struct SegT { int s; }t[400010]; int read() { out=0,c=getchar(); while(c<48||c>57){c=getchar();} while(c>=48&&c<=57){out=(out<<3)+(out<<1)+(c&15),c=getchar();} return out; } void Add(int x,int y) { e[++cnt].next=h[x], e[cnt].to=y, h[x]=cnt; } void DFS1(int x) { dep[x]=dep[dad[x]]+1,size[x]=1; for(int i=h[x];i;i=e[i].next) { int y=e[i].to; if(y^dad[x]) { dad[y]=x; DFS1(y); size[x]+=size[y], son[x]=size[y]>size[son[x]]?y:son[x]; } } } void DFS2(int x) { id[x]=++tot, top[x]=x==son[dad[x]]?top[dad[x]]:x; if(!son[x]){return;} DFS2(son[x]); for(int i=h[x];i;i=e[i].next) { int y=e[i].to; if(y^dad[x]&&y^son[x]){DFS2(y);} } } void DFS(int x) { DFS1(x); DFS2(x); } void Pushup(int k) { t[k].s=t[k<<1].s+t[k<<1|1].s; } void Change(int k,int l,int r,int p,int x) { if(l==r) { t[k].s=x; return; } int mid=l+r>>1; if(p<=mid){Change(k<<1,l,mid,p,x);} else{Change(k<<1|1,mid+1,r,p,x);} Pushup(k); } int Query(int k,int l,int r,int ll,int rr) { if(r<ll||rr<l){return 0;} if(ll<=l&&r<=rr){return t[k].s;} int mid=l+r>>1; return Query(k<<1,l,mid,ll,rr)+Query(k<<1|1,mid+1,r,ll,rr); } int LCA(int x,int y) { int ans=0,now; while(top[x]^top[y]) { if(dep[top[x]]<dep[top[y]]){x^=y,y^=x,x^=y;} now=Query(1,1,n,id[top[x]],id[x]); if(now){return -1;} ans+=id[x]-id[top[x]]+1; x=dad[top[x]]; } if(dep[x]>dep[y]){x^=y,y^=x,x^=y;} now=Query(1,1,n,id[x]+1,id[y]); if(now){return -1;} ans+=id[y]-id[x]; return ans; } int main() { n=read(); for(int i=1;i<n;++i) { u[i]=read(),v[i]=read(); Add(u[i],v[i]);Add(v[i],u[i]); } DFS(1); m=read(); while(m--) { opt=read(); if(opt==1) { x=read(); if(dep[u[x]]>dep[v[x]]){Change(1,1,n,id[u[x]],0);} else{Change(1,1,n,id[v[x]],0);} } if(opt==2) { x=read(); if(dep[u[x]]>dep[v[x]]){Change(1,1,n,id[u[x]],1);} else{Change(1,1,n,id[v[x]],1);} } if(opt==3) { x=read(),y=read(); printf("%d\n",LCA(x,y)); } } return 0; }
原文：https://www.cnblogs.com/zzWutianyu/p/14766646.html