Description

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：

标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）

你能帮帮他吗?

Input

输入第一行两个正整数N和Q分别表示节点个数和操作次数

接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边

接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。

Output

输出一个正整数，表示结果

Sample Input

5 5

1 2

1 3

2 4

2 5

Q 2

C 2

Q 2

Q 5

Q 3

Sample Output

1

2

2

1

HINT

30%的数据，1 ≤ N, Q ≤ 1000

70%的数据，1 ≤ N, Q ≤ 10000

100%的数据，1 ≤ N, Q ≤ 100000

---

想法

这道题的做法其实挺多的……先说我自己的吧

先dfs一遍，记录dfs序

用线段树维护到结点最近的已标记祖先编号

每次标记操作，就更新它的子节点的最近已标记祖先编号（用lazy）

查询某个点就从根节点往下走，不断pushdown，更新下面结点的最近已标记祖先，一直走到要查询的那个点。

复杂度O(QlogN)

还有一种不错的做法。

把所有操作读入，要标记的节点先都标记上

dfs一遍。记录每个节点的它最近的已标记祖先（包括自己），并查集并在一起

从后往前处理每个操作。

若是标记操作，便把这个标记去掉，将它与父节点并在一起，表明它与它父节点的最近已标记祖先是同一个点。

若是查询操作，这个点的最近已标记祖先便为它所在并查集的根。

这个做法应该比线段树快，但不太好想到。

---

代码

（线段树版）

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 100005;struct node{    int v;    node *next;       }pool[N],*h[N];int cnt;void addedge(int u,int v){    node *p=&pool[++cnt];    p->v=v;p->next=h[u];h[u]=p;     }int dep[N],dfn[N],out[N];int tot;void dfs(int u){    int v;    dfn[u]=++tot;    for(node *p=h[u];p;p=p->next)        if(!dep[v=p->v]){            dep[v]=dep[u]+1;            dfs(v);                    }    out[u]=tot;}struct tree{    tree *ch[2];    int v;       }pool2[N*20],*root;int cnt2;void pushdown(tree *p){    if(dep[p->v]>dep[p->ch[0]->v]) p->ch[0]->v=p->v;    if(dep[p->v]>dep[p->ch[1]->v]) p->ch[1]->v=p->v;     }void build(tree *p,int l,int r){    p->v=1;    if(l==r) return;    int mid=(l+r)>>1;    build(p->ch[0]=&pool2[++cnt2],l,mid);    build(p->ch[1]=&pool2[++cnt2],mid+1,r);     }void change(tree *p,int l,int r,int L,int R,int c){    if(dep[c]
       
        v]) return;    if(l==L && r==R){        if(dep[c]>dep[p->v]) p->v=c;        return;    }    pushdown(p);    int mid=(l+r)>>1;    if(mid>=R) change(p->ch[0],l,mid,L,R,c);    else if(mid
        
         ch[1],mid+1,r,L,R,c);    else {        change(p->ch[0],l,mid,L,mid,c);        change(p->ch[1],mid+1,r,mid+1,R,c);         }}int query(tree *p,int l,int r,int L){    if(l==L && r==L) return p->v;    pushdown(p);    int mid=(l+r)>>1;    if(mid>=L) return query(p->ch[0],l,mid,L);    return query(p->ch[1],mid+1,r,L);  }int n,q;int main(){    char ch;    int u,v;    scanf("%d%d",&n,&q);    for(int i=1;i