[LuoguP3950] 部落冲突

emmmm虽然上次被线段树合并给恶心了qwq但是还是不能放弃数据结构呀。于是记录一下树链剖分吧哈哈哈哈，比较好想的一道模板题目，被输入卡了很多TOO SHORT ON LINE 1emmmm最后把scanf(“%c%c%d”,&tmp,&c,&x);改成了scanf(“%c”,s,&x);就可以了，看来是windows编程环境与linux评测环境的问题emmm

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define mid ((l+r)>>1)
#define maxn 300005
using namespace std;
struct node{
    int to;
    node*next;
}*con[maxn];
void addedge(int x,int y){
    node*p=new node;
    p->to=y;
    p->next=con[x];
    con[x]=p;
}
int n,m,x,y,tim,zz;
bool vis[maxn];
int sz[maxn],hs[maxn],hd[maxn],fa[maxn],de[maxn],dfn[maxn];
struct segtree;
segtree *Nul;
struct segtree{
    int sum,lazy;
    segtree*so[2];
    segtree(){
        so[0]=so[1]=Nul;
        sum=0;
    }
    void update() {sum=so[0]->sum+so[1]->sum;}
    void build(int l,int r){
        if(l==r) return;
        (so[0]=new segtree)->build(l,mid);
        (so[1]=new segtree)->build(mid+1,r);
        update();
    }
    void calc(int l,int r,int tag){
        lazy+=tag;
        sum+=(r-l+1)*tag;
    }
    void pushdown(int l,int r){
        if(so[0]!=Nul) so[0]->calc(l,r,lazy);
        if(so[1]!=Nul) so[1]->calc(l,r,lazy);
        lazy=0;
    }
    void modify(int l,int r,int lx,int rx,int num){
 //     cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
        if(l==lx&&r==rx){
            calc(l,r,num);
            return;
        }
        pushdown(l,r);
        if(lx>mid) so[1]->modify(mid+1, r, lx, rx, num);
        else if(rx<=mid) so[0]->modify(l, mid, lx, rx, num);
        else {so[0]->modify(l, mid, lx, mid, num);so[1]->modify(mid+1, r, mid+1, rx, num);}
        update();
    }
    int query(int l,int r,int lx,int rx){
        if(l==lx&&r==rx)
            return sum;
        pushdown(l,r);
        if(lx>mid) return so[1]->query(mid+1,r,lx,rx);
        else if(rx<=mid) return so[0]->query(l,mid,lx,rx);
        else return so[0]->query(l,mid,lx,mid)+so[1]->query(mid+1,r,mid+1,rx);
    }
}*xtr;
void dfs1(int v){
    vis[v]=true;
    int mxsz=0;
    sz[v]=1;
    for(node*p=con[v];p;p=p->next)
        if(!vis[p->to]) {
            fa[p->to]=v;
            de[p->to]=de[v]+1;
            dfs1(p->to);
            sz[v]+=sz[p->to];
            if(sz[p->to]>mxsz) {hs[v]=p->to;mxsz=sz[p->to];}
        }
    return;
}
void dfs2(int v){
    vis[v]=true;
    dfn[v]=++tim;
    for(node*p=con[v];p;p=p->next)
        if(hs[v]==p->to) {
            hd[p->to]=hd[v];
            dfs2(p->to);
        }
    for(node*p=con[v];p;p=p->next)
        if(!vis[p->to]&&hs[v]!=p->to)
            dfs2(p->to);
}
bool qry(int x,int y){
    while(hd[x]!=hd[y]){
        if(de[hd[x]]<de[hd[y]]) swap(x,y);
        if(xtr->query(1,n,dfn[hd[x]],dfn[x])) return false;
        x=fa[hd[x]];
    }
    if(x==y){
        return true;
    }
    if(de[x]<de[y]) swap(x,y);
    if(xtr->query(1,n,dfn[y]+1,dfn[x])) return false;
    return true;
}
void war(int x,int y,int tmp){
    while(hd[x]!=hd[y]){
        if(de[hd[x]]<de[hd[y]]) swap(x,y);
        xtr->modify(1, n, dfn[hd[x]], dfn[x], tmp);
        x=fa[hd[x]];
    }
    if(x==y) return;
    if(de[x]<de[y]) swap(x,y);
    xtr->modify(1, n, dfn[y]+1, dfn[x], tmp);
}
struct suibian{
    int x,y;
}wrs[maxn];
int main(){
    scanf("%d%d",&n,&m);
    Nul=new segtree;
    Nul->so[0]=Nul;Nul->so[1]=Nul;Nul->lazy=Nul->sum=0;
    (xtr=new segtree)->build(1,n);
    for(int i=1;i<=n;++i) hd[i]=i;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    de[1]=1;
    dfs1(1);
    memset(vis,0,sizeof(vis));
    dfs2(1);
    char s[5],c;
    while(m--){
        scanf("%s%d",s,&x);
        if(s[0]=='Q'){
            scanf("%d",&y);
            if(qry(x,y)) printf("Yes\n");
            else printf("No\n");
        }
        if(s[0]=='C'){
            scanf("%d",&y);
            wrs[++zz].x=x;wrs[zz].y=y;
            war(x,y,1);
        }
        if(s[0]=='U')
            war(wrs[x].x,wrs[x].y,-1);
    }
    return 0;
}