[文章目录]
Description
在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）你能帮帮他吗?1 ≤ N, Q ≤ 100000，没有强制在线。
强制在线的话可以线段树标记永久化维护dfs序，以打标记的点的dep为时间戳，更新子树dfs序区间。查询时，找最大时间戳对应的点即可。
不在线直接将操作倒过来，并查集维护一下就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int fa[N],f[N],siz[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void dfs(int x,int pre)
{
fa[x]=pre;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
dfs(to[i],x);
}
struct ques
{
int fl,x,ans;
}q[N];
int main()
{
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
for(i=1;i<=n;++i) f[i]=fa[i];
char sw[10];
for(i=1;i<=m;++i)
{
scanf("%s%d",sw,&q[i].x);
q[i].fl=(sw[0]=='Q');
if(!q[i].fl) f[q[i].x]=q[i].x,siz[q[i].x]++;
}
f[1]=1; siz[1]++;
for(i=m;i;--i)
{
if(q[i].fl) q[i].ans=find(q[i].x);
else
{
siz[q[i].x]--;
if(!siz[q[i].x]) f[q[i].x]=fa[q[i].x];
}
}
for(i=1;i<=m;++i) if(q[i].fl) printf("%d\n",q[i].ans);
return 0;
}