http://www.lydsy.com/JudgeOnline/problem.php?id=4551
题目描述
给定一棵有根树（根为 1），有以下两种操作：
1. 标记操作:对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。
输入格式
输入第一行两个正整数 和
分别表示节点个数和操作次数
接下来 行，每行两个正整数
表示
到
有一条有向边
接下来 行，“
”时表示这是一个标记操作,为“
”时表示这是一个询问操作,
输出格式
对于每一个询问操作，输出一个正整数，表示结果。
输入样例
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
输出样例
1
2
2
1
数据范围
题解
初始时打好所有标记，逆序处理，用并查集维护，当遇到一个询问操作时，把标记 ，若此时标记变为
，则将该点与父亲节点合并。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 1500005
#define depth 32
using namespace std;
int n,q,tot;
struct hh
{int to,next;}e[N<<1];
int fa[N],dep[N],col[N],last[N],f[N],opt[N],x[N],ans[N];
void add(int a,int b)
{
e[++tot].to=b;
e[tot].next=last[a];
last[a]=tot;
}
void dfs(int now)
{
int i;
for(i=last[now];i;i=e[i].next)
if(!dep[e[i].to])
{
dep[e[i].to]=dep[now]+1;
fa[e[i].to]=now;
dfs(e[i].to);
}
}
int read()
{
int ret=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main()
{
int i,j,u,v,fx,fy;
char flag;
n=read();q=read();
for(i=1;i<=n-1;i++)
{
u=read();v=read();
add(u,v); add(v,u);
}
dfs(1);
for(i=1;i<=q;i++)
{
scanf("\n%c",&flag);
if(flag=='C') opt[i]=1;
else opt[i]=2;
x[i]=read();
}
dep[1]=1;col[1]=1;
for(i=1;i<=q;i++)
if(opt[i]==1) col[x[i]]++;
for(i=1;i<=n;i++) f[i]=i;
for(i=2;i<=n;i++)
if(!col[i]) f[find(i)]=find(fa[i]);
for(i=q;i>=1;i--)
if(opt[i]==2) ans[++ans[0]]=find(x[i]);
else
{
col[x[i]]--;
if(!col[x[i]]) f[find(x[i])]=find(fa[x[i]]);
}
for(i=ans[0];i>=1;i--)
printf("%d\n",ans[i]);
return 0;
}