[HEOI2016/TJOI2016]树

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

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

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

你能帮帮她吗?

输入格式
第一行两个正整数 NN 和 QQ 分别表示节点个数和操作次数。

接下来 N-1N−1 行，每行两个正整数 u,v ,, (1 \leqslant u,v \leqslant n)u,v(1⩽u,v⩽n) 表示 uu 到 vv 有一条有向边。

接下来 QQ 行，形如 oper num ，oper 为 C 时表示这是一个标记操作, oper 为 Q 时表示这是一个询问操作。

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

输入输出样例
输入 #1复制
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3

输出 #1复制
1
2
2
1

说明/提示

30%30% 的数据，1 \leqslant N, Q \leqslant 10001⩽N,Q⩽1000 ；

70%70% 的数据，1 \leqslant N, Q \leqslant 100001⩽N,Q⩽10000 ；

100%100% 的数据，1 \leqslant N, Q \leqslant 1000001⩽N,Q⩽100000 。

考虑树剖：
我们可以知道，树剖链上的一定是当前点的祖先。然后我们一直树剖跳链即可。

如果当前链的和大于1，则证明有被标记的点，然后二分找到深度最大的即可。

树状数组维护链上的和即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e5+10;
int n,q,d[N];
int head[N],nex[N<<1],to[N<<1],tot;
int pos[N],h[N],bl[N],sz[N],f[N],son[N],cnt,vis[N];
inline void ade(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
inline void add(int x,int v){for(;x<=n;x+=lowbit(x)) d[x]+=v;}
inline int ask(int x){int s=0;for(;x;x-=lowbit(x)) s+=d[x]; return s;}
int sum(int l,int r){return ask(r)-ask(l-1);}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(f[x]==to[i])	continue;
		f[to[i]]=x; h[to[i]]=h[x]+1;
		dfs1(to[i]); sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]]) son[x]=to[i];
	}
}
void dfs2(int x,int belong){
	pos[x]=++cnt; bl[x]=belong; vis[cnt]=x;
	if(!son[x])	return ; dfs2(son[x],belong);
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);
}
int solve(int l,int r){
	while(l<r){
		int mid=l+r+1>>1;
		if(sum(mid,r))	l=mid;
		else	r=mid-1;
	}
	return vis[l];
}
inline int query(int x){
	while(x){
		if(sum(pos[bl[x]],pos[x]))	return solve(pos[bl[x]],pos[x]);
		x=f[bl[x]];
	}
}
signed main(){
	cin>>n>>q;
	for(int i=1,x,y;i<n;i++)	scanf("%d %d",&x,&y),ade(x,y),ade(y,x);
	dfs1(1); dfs2(1,1); add(pos[1],1);
	while(q--){
		char op[2]; int x;	scanf("%s %d",op,&x);
		if(op[0]=='Q')	printf("%d\n",query(x));
		else	add(pos[x],1);
	}
	return 0;
}