简单起见，你就是要处理下面三件事，所有的事件都是按照时间顺序给出的。
Q p q 从第 pp 个部落出发的建筑工人想知道能否到达第 qq 个部落了，你要回答的便是 Yes / No，注意大小写。
C p q 第 pp 个部落与第 qq 个部落开战了，保证他们一定是相邻的部落，且目前处于停战（未开战）状态。
U x 第 xx 次发生的战争结束了，它将永远的被载入史册，不复存在（保证这个消息不会告诉你多次）
第一行两个数 nn 和 mm， nn 代表了一共有 nn 个部落，mm 代表了以上三种事件发生的总数。
接下来的 n - 1n−1 行，每行两个数 p, qp,q，代表了第 pp 个部落与第 qq 个部落之间有一条道路相连。
接下来的 mm 行，每行表示一件事，详见题目描述。
每行一个 Yes 或者 No，表示从第 pp 个部落出发的建筑工人能否到达第 qq 个部落。
#include<bits/stdc++.h> using namespace std; const int maxn=3e5+100; vector<int> g[maxn]; struct war { int u,v; }War[maxn]; int n,m; int son[maxn]; int id[maxn]; int fa[maxn]; int cnt; int dep[maxn]; int size[maxn]; int top[maxn]; int w[maxn]; int wt[maxn]; struct node { int l,r; int sum; int lazy; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=wt[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } void spread (int i) { if (segTree[i].lazy) { segTree[i<<1].sum+=segTree[i].lazy*(segTree[i<<1].r-segTree[i<<1].l+1); segTree[i<<1|1].sum+=segTree[i].lazy*(segTree[i<<1|1].r-segTree[i<<1|1].l+1); segTree[i<<1].lazy+=segTree[i].lazy; segTree[i<<1|1].lazy+=segTree[i].lazy; segTree[i].lazy=0; } } void update (int i,int l,int r,int val) { if (l<=segTree[i].l&&segTree[i].r<=r) { segTree[i].sum+=val*(segTree[i].r-segTree[i].l+1); segTree[i].lazy+=val; return; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) update(i<<1,l,r,val); if (r>mid) update(i<<1|1,l,r,val); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } int query (int i,int l,int r) { if (l<=segTree[i].l&&segTree[i].r<=r) return segTree[i].sum; spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; int ans=0; if (l<=mid) ans+=query(i<<1,l,r); if (r>mid) ans+=query(i<<1|1,l,r); return ans; } int qRange (int x,int y) { int ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,id[top[x]],id[x]); if (ans) return ans; x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans+=query(1,id[x]+1,id[y]); return ans; } void upRange (int x,int y,int k) { //修改整条路径 while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,id[top[x]],id[x],k); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,id[x]+1,id[y],k); } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1;//记录重儿子的儿子数 for (int y:g[x]) { if (y==f) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int y:g[x]) { if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main () { scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); int tot=0; for (int i=1;i<=m;i++) { string s; cin>>s; if (s=="Q") { int x,y; scanf("%d%d",&x,&y); int ans=qRange(x,y); if (ans) printf("No\n"); else printf("Yes\n"); } else if (s=="C") { int x,y; scanf("%d%d",&x,&y); War[++tot]={x,y}; upRange(x,y,1); } else if (s=="U") { int x; scanf("%d",&x); upRange(War[x].u,War[x].v,-1); } } }
原文：https://www.cnblogs.com/zhanglichen/p/13479567.html