题目描述

给定一棵有根树（根为 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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 1500005#define depth 32using 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;}