题目描述

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

输入

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

输出

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

样例输入

5 5

1 2

1 3

2 4

2 5

Q 2

C 2

Q 2

Q 5

Q 3

样例输出

1

2

2

1

---

题解

在线的话可以树剖，然而我选择了离线并查集。

加标记比较难搞，我们可以换一种思路，先把所有标记加进来，再从后往前删掉。

每个节点的f为最近的有标记的祖先，这可以在dfs中直接实现。

然后从后往前处理，如果是修改则删标记，删为0时直接将该点的f赋为f[fa]。

如果是查询，直接记录find即可。

理论时间复杂度O(αN)，然而这么慢也是醉了。

另外听说暴力可过。

#include 
     
      #include 
      
       #define N 100010using namespace std;int head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , t[N] , f[N] , opt[N] , p[N] , ans[N];char str[5];void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x , int last){	if(t[x]) last = x;	f[x] = last;	int i;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x])			fa[to[i]] = x , dfs(to[i] , last);}int find(int x){	return x == f[x] ? x : f[x] = find(f[x]);}int main(){	int n , m , i , x , y;	scanf("%d%d" , &n , &m);	for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);	t[1] = 1;	for(i = 1 ; i <= m ; i ++ )	{		scanf("%s%d" , str , &p[i]);		if(str[0] == 'C') opt[i] = 1 , t[p[i]] ++ ;	}	dfs(1 , 0);	for(i = m ; i >= 1 ; i -- )	{		if(opt[i])		{			t[p[i]] -- ;			if(!t[p[i]]) f[p[i]] = f[fa[p[i]]];		}		else ans[i] = find(p[i]);	}	for(i = 1 ; i <= m ; i ++ ) if(!opt[i]) printf("%d\n" , ans[i]);	return 0;}