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 3Sample Output
1
2
2
1题目分析：
这道题可以离线询问用并查集搞 ：每个点存储非自己，并离自己最近的标记点 。
删除标记时：如果标记删没了 就把并查集更改为：f[x]==fa[x]。
询问就直接find()就好了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
char s[2];
int f[110000],fa[110000];
int net[210000],head[110000],to[210000];
int flag[110000];
int tot;
void add(int x,int y)
{
net[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
struct your
{
int tmp;
int x;
}a[110000];
int ans[110000];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void dfs(int x,int temp,int dx)
{
fa[x]=dx;
if(flag[x]) f[x]=x,dx=x;
else f[x]=dx;
for(int i=head[x];i;i=net[i])
if(to[i]!=temp) dfs(to[i],x,dx);
}
int main()
{
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);
}
flag[1]=1;
fa[1]=1;
for(int i=1;i<=m;i++)
{
scanf("%s",&s[0]);
scanf("%d",&a[i].x);
if(s[0]=='C')
{
flag[a[i].x]++;
a[i].tmp=1;
}
else a[i].tmp=2;
}
dfs(1,0,1);
for(int i=m;i>=1;i--)
{
ans[i]=-1;
if(a[i].tmp==1)
{
flag[a[i].x]--;
if(!flag[a[i].x]) f[a[i].x]=fa[a[i].x];
}
else ans[i]=find(a[i].x);
}
for(int i=1;i<=m;i++)
if(ans[i]!=-1) printf("%d\n",ans[i]);
}
