\[\text{关于题意} \]

\(\quad\)一道很简单的树剖题，只有三种操作(其实是两种)，唯一要考虑的点是如何将边权转化成点权，考虑到每个点都有且只有一个父亲节点(除根节点1之外)，那么我们就可以将父亲与儿子连接的边权记录到儿子身上，这样 \(n-1\) 条边就可以合理的分配到 \(n-1\) 个点上(除了根节点)，这样就转化成了普通的树链剖分模板了(如果还不能理解就看看图吧)。

原图

经过转化后的图(将边权转化为点权)

注意：对于路径\(4-2-5\)，只需访问点 \(4\) 和点 \(5\)，对于 \(4\) 和 \(5\) 的 \(LCA\) (最近公共祖先)不可取，因为 \(2\) 在原图中对应的是边 \(1-2\)，并不在路径\(4-2-5\)上，所以在树链剖分中当 \(x\) 和 \(y\) 在同一条链上时(\(dep[x]<dep[y]\))，只需询问 \(x+1\) 到 \(y\) 的路径。

\[\text{对于三种操作} \]

1. 操作 \(1\)：单点修改，两个相邻的部落开战，他们之间的道路不可通行。

2. 操作 \(2\)：区间询问，询问两个点之间的路径能否通行。

3. 操作 \(3\)：单点修改，两个开战的部落停战，他们之间的道路可以通行。

\(\quad\)可以很容易发现操作 \(1\)和操作 \(3\) 其实是一种操作，只需开一个数组 \(u\)[\(x\)][\(2\)] 来记录参与第\(x\)次战争的两个部落，开战将这条边标记为 \(0\)，意为不可通行，停战就把这条边标记为 \(1\)，意为可以通行，用线段树维护区间和(也可以是最小值)，当\(sum\)[\(k\)]==\(r\)-\(l\)+\(1\) 时说明这个区间内所有边皆可通行，否则至少有\(1\)条边不可通行。

\(\quad\)下面贴出AC代码，建议反复阅读，深刻理解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define il inline
#define inf 1e18
#define next nne
#define re register int
using namespace std;
il int read()				//快速读入
{
	int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
const int N=3e5+5;
int n,m,next[N<<1],go[N<<1],head[N],tot,u[N][2],sum[N<<2];
int seg[N],son[N],father[N],top[N],size[N],dep[N];
il void Add(int x,int y)		//链式前向星存图
{
  next[++tot]=head[x];
  head[x]=tot;
  go[tot]=y;
}
il void dfs1(int x,int fa)
{
  father[x]=fa;dep[x]=dep[fa]+1;size[x]=1;
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(y==fa)continue;
      dfs1(y,x);
      size[x]+=size[y];
      if(size[y]>size[son[x]])son[x]=y;
    }
}
il void dfs2(int x,int topf)
{
  top[x]=topf;seg[x]=++seg[0];
  if(!son[x])return;
  dfs2(son[x],topf);
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(top[y])continue;
      dfs2(y,y);
    }
}
il void build(int k,int l,int r)	//建树，每个点初始值为1
{
  if(l==r){sum[k]=1;return;}
  int mid=l+r>>1;
  build(k<<1,l,mid);build(k<<1|1,mid+1,r);
  sum[k]=sum[k<<1]+sum[k<<1|1];
}
il void change(int k,int l,int r,int x,int z)
{
  if(l==r){sum[k]=z;return;}
  int mid=l+r>>1;
  if(x<=mid)change(k<<1,l,mid,x,z);
  else change(k<<1|1,mid+1,r,x,z);
  sum[k]=sum[k<<1]+sum[k<<1|1];
}
il bool query1(int k,int l,int r,int x,int y)
{
  if(x<=l&&y>=r){if(sum[k]==r-l+1)return 1;return 0;}
  int mid=l+r>>1;
  if(x<=mid)if(!query1(k<<1,l,mid,x,y))return 0;
  if(y>mid)if(!query1(k<<1|1,mid+1,r,x,y))return 0;
  return 1;
}
il void change1(int x,int y)
{
  if(father[x]==y)change(1,1,n,seg[x],0);//修改儿子节点
  else change(1,1,n,seg[y],0);
}
il void change2(int x)
{
  int xx=u[x][0],yy=u[x][1];
  if(father[xx]==yy)change(1,1,n,seg[xx],1);//修改儿子节点
  else change(1,1,n,seg[yy],1);
}
il bool query(int x,int y)
{
  int fx=top[x],fy=top[y];
  while(fx!=fy)
    {
      if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
      if(!query1(1,1,n,seg[fx],seg[x]))return 0;
      x=father[fx];fx=top[x];
    }
  if(dep[x]>dep[y])swap(x,y);
  if(seg[x]+1<=seg[y])if(!query1(1,1,n,seg[x]+1,seg[y]))return 0;		//注意seg[x]要+1，
  return 1;
}
signed main()
{
  n=read();m=read();
  for(re i=1;i<n;i++){re x=read(),y=read();Add(x,y);Add(y,x);}
  dfs1(1,0);dfs2(1,1);build(1,1,n);tot=0;
  while(m--)
    {
      char ch;cin>>ch;
      if(ch=='C'){u[++tot][0]=read();u[tot][1]=read();change1(u[tot][0],u[tot][1]);}
      else if(ch=='Q'){re x=read(),y=read();if(query(x,y))puts("Yes");else puts("No");}
      else {re x=read();change2(x);}
    }
  return 0;
}

\[\text{后话} \]

\(\quad\)此题和CF165D Beard Graph很像，那题也有我的题解，欢迎支持。

\(\quad\)谢谢观赏，写题解不易，点个赞吧！