Aizu 2170 Marked Ancestor（并查集变形）-白红宇

Aizu 2170 Marked Ancestor（并查集变形）

阅读量：5207 次

发布时间：2019-06-14

本文共 1157 字，大约阅读时间需要 3 分钟。

寻找根节点很容易让人联想到DisjointSet，但是DisjointSet只有合并操作，

所以询问离线倒着考虑，标记会一个一个消除，这时候就变成合并了。

因为询问和查询的时间以及标记生效的时间有关，记录下查询时间，在树上记录的标记。（没有做标记的默认为最大询问时间+1，根节点为0

在Find的时候根据询问的时间进行回答。

路径压缩会影响到答案吗？并不会，因为压缩的时候，标记一定已经失效了。

（答案会爆int，这种问题无非就是在路径上做一些改动，类似比如UVA 11987 Almost Union-Find。分开操作，一般都逆序变成合并

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                //#include
                
                 using namespace std;const int maxn = 1e5+5;int pa[maxn];int Mrk[maxn];int qt[maxn],qv[maxn];int Qt;int fdst(int x){ return Mrk[x] < Qt ? x :pa[x] = fdst(pa[x]);}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int N, Q; while(scanf("%d%d",&N,&Q),N){ for(int i = 2; i <= N; i++){ scanf("%d",pa+i); Mrk[i] = Q+1; } int c = 0; for(int i = 1; i <= Q; i++){ char op[2]; int v; scanf("%s%d",op,&v); if(*op == 'Q'){ qt[c] = i; qv[c++] = v; }else { Mrk[v] = min(Mrk[v],i);//取最早生效的标记 } } long long ans = 0; while(c--){ Qt = qt[c]; ans += fdst(qv[c]); } printf("%lld\n",ans); } return 0;}

转载于:https://www.cnblogs.com/jerryRey/p/4889510.html

你可能感兴趣的文章