Description

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）你能帮帮他吗?

Input

输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v 有一条有向边接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询 问操作对于每次询问操作，1 ≤ N, Q ≤ 100000。

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

分析

这题用并查集也可以做，那我们就讲讲并查集的算法 如果我们按正常的顺序套并查集，那么我们只能将所有的点的f都指向他最近的打了标记的祖先，但这样就没法进行区间合并了 于是我们不妨反过来删标记，先把所有打了标记的点的f都指向自己，其余的都指向它的父节点，然后从后往前处理询问。如果是删除，那么去掉该点的标记，当一个点失去所有标记时，就将它与父节点合并。如果是询问，直接find(x)就好了 其实也可以线段树+树剖

代码

#include <bits/stdc++.h> #define N 100010 struct NOTE { int to,next; }e[N * 2]; int cnt; int next[N]; struct Q { int id; bool f; }q[N]; int fa[N],f[N]; int ans[N],times[N]; void add(int x,int y) { e[++cnt].to = y; e[cnt].next = next[x]; next[x] = cnt; } int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } void dfs(int x) { if (times[x]) f[x] = x; else f[x] = fa[x]; for (int i = next[x]; i; i = e[i].next) { int u = e[i].to; if (u != fa[x]) { fa[u] = x; dfs(u); } } } int main() { int n,m; scanf("%d%d",&n,&m); for (int i = 1; i < n; i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } times[1] = 1; for (int i = 1; i <= m; i++) { char ch[5]; scanf("%s%d",ch,&q[i].id); if (ch[0] == 'C') { times[q[i].id]++; q[i].f = true; } } dfs(1); for (int i = m; i; i--) { int id = q[i].id; if (q[i].f) { times[id]--; if (!times[id]) f[id] = fa[id]; } else ans[i] = find(id); } for (int i = 1; i <= m; i++) if (ans[i]) printf("%d\n",ans[i]); }