首页 > 其他 > 详细

BZOJ 4551: [Tjoi2016&Heoi2016]树 并查集(&&图论?)

时间:2019-04-18 00:40:24      阅读:113      评论:0      收藏:0      [点我收藏+]

反向操作,先把所有的标记都打上(记得统计标记的数目),然后依次撤销,合并到自己的上一个点pre,即fa[u]=getf(pre[u])

#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
const int N=100010;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==-?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,k,cnt;
int vr[N<<1],nxt[N<<1],fir[N],fa[N],pre[N],c[N],ans[N],s[N];
char ch[N];
inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}
int getf(int x) {return x==fa[x]?x:fa[x]=getf(fa[x]);}
void dfs(int u,int f) { bool flg=true;
    if(!fa[u]) fa[u]=f,flg=false;
    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
        if(pre[v]) continue; pre[v]=u;
        if(flg) dfs(v,u);
        else dfs(v,f);
    }
}
signed main() {
    n=g(),k=g();
    for(R i=1,u,v;i<n;++i) u=g(),v=g(),add(u,v),add(v,u);
    for(R i=1;i<=k;++i) {
        while(!isalpha(ch[i]=getchar())); c[i]=g(); 
        if(ch[i]==C) fa[c[i]]=c[i],++s[c[i]];
    } fa[1]=1; pre[1]=1;
    dfs(1,1); cnt=0;
    for(R i=k;i>=1;--i) {
        if(ch[i]==C&&!(--s[c[i]])) fa[c[i]]=getf(pre[c[i]]);
        else if(ch[i]==Q)ans[++cnt]=getf(c[i]);
    } for(R i=cnt;i>=1;--i) printf("%d\n",ans[i]);
}

2019.04.16

BZOJ 4551: [Tjoi2016&Heoi2016]树 并查集(&&图论?)

原文:https://www.cnblogs.com/Jackpei/p/10727113.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!