Description

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下

两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个

结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖

先）你能帮帮他吗?

Solution

还是非常巧妙的思维

离线，先记录每个点的标记数，倒序处理询问，遇到打标记就把标记数减一，对于标记数为0的点就用并查集与它的父节点合并

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100005using namespace std;int n,q,head[MAXN],cnt=0,f[MAXN],father[MAXN],num[MAXN],sign[MAXN];char opt[MAXN];vector
          
           v;struct Node{ int next,to;}Edges[MAXN*2];void addedge(int u,int v){ Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v;}int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); } return x*f;}int find(int x){ if(father[x]==x)return x; return father[x]=find(father[x]);}void dfs(int u){ if(!sign[u])father[u]=find(f[u]); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f[u])continue; f[v]=u; dfs(v); }}int main(){ memset(head,-1,sizeof(head)); n=read(),q=read(); for(int i=1;i
           
            0;i--) { if(opt[i]=='C') { sign[num[i]]--; if(!sign[num[i]]) father[num[i]]=find(f[num[i]]); } else v.push_back(find(num[i])); } for(int i=v.size()-1;i>=0;i--) printf("%d\n",v[i]); return 0;}