NOIP太可怕了((( -口-)
【题目大意】
给定一颗有根树(根为1),有以下两种操作:
1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)
2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先) 【思路】正着做不行就反方向来。先离线处理所有操作,算出最终某个点被标记了几次。跑一次dfs算出最终状态时每个点最近的打了标记的祖先u[i]。从后往前重新看操作,如果是标记操作,那么当前节点标记数-1,如果标记数为0了,那么u[i]=fa[i]最近的祖先(用并查集来处理之前的更新)。如果为询问,则输出当前最近的祖先(同样可以用并查集来做)。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=+;
vector<int> E[MAXN];
int mark[MAXN];
int query[MAXN],ans[MAXN];
int u[MAXN],fa[MAXN],n,q;
char op[MAXN]; void dfs(int x,int anc,int father)
{
fa[x]=father;
if (mark[x]>) u[x]=x;
else u[x]=anc;
for (int i=;i<E[x].size();i++)
{
int to=E[x][i];
if (to==fa[x]) continue;
dfs(to,u[x],x);
}
} int union_set(int x)
{
int r=x;
while (u[r]!=r) r=u[r];
int now=x;
while (u[now]!=r)
{
int tmp=u[now];
u[now]=r;
now=tmp;
}
return u[x];
} void init()
{
scanf("%d%d",&n,&q);
for (int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
E[u].push_back(v);
E[v].push_back(u);
}
mark[]=;
for (int i=;i<=q;i++)
{
char tmp[];
scanf("%s %d",tmp,&query[i]);
if (tmp[]=='C') mark[query[i]]++;
op[i]=tmp[];
}
dfs(,,);
for (int i=;i<=n;i++) cout<<u[i]<<endl;
} void solve()
{
memset(ans,,sizeof(ans));
for (int i=q;i>=;i--)
{
int now=query[i];
if (op[i]=='C')
{
mark[now]--;
if (!mark[now]) now=union_set(fa[now]);
}
else ans[++ans[]]=union_set(now);
}
for (int i=ans[];i>=;i--) printf("%d\n",ans[i]);
} int main()
{
init();
solve();
return ;
}