[HDU]4694 Important Sisters（支配树）

支配树模板

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
inline int read()
{
    int x;char c;
    while((c=getchar())<'0'||c>'9');
    for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
    return x;
}
#define MN 50000
#define MM 100000
struct ZPS
{
    struct edge{int nx,t;}e[MM*2+MN+5];
    int h[MN+5],rh[MN+5],v[MN+5],en,fa[MN+5],d[MN+5],p[MN+5],cnt;
    int id[MN+5],sd[MN+5],f[MN+5],mn[MN+5];
    inline void ins(int*h,int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
    inline void ins(int x,int y){ins(h,x,y);ins(rh,y,x);}
    void dfs(int x)
    {
        p[d[x]=++cnt]=x;
        for(int i=h[x];i;i=e[i].nx)if(!d[e[i].t])fa[e[i].t]=x,dfs(e[i].t);
    }
    int gf(int x)
    {
        if(!f[x])return x;
        int ff=gf(f[x]);
        if(sd[mn[f[x]]]<sd[mn[x]])mn[x]=mn[f[x]];
        return f[x]=ff;
    }
    void build(int s)
    {
        dfs(s);
        for(int i=1;i<=cnt;++i)sd[i]=mn[i]=i;
        for(int i=cnt;i>1;--i)
        {
            for(int j=rh[p[i]];j;j=e[j].nx)if(d[e[j].t])
                gf(d[e[j].t]),sd[i]=min(sd[i],sd[mn[d[e[j].t]]]);
            ins(v,sd[i],i);f[i]=d[fa[p[i]]];
            for(int&j=v[f[i]];j;j=e[j].nx)
                gf(e[j].t),id[e[j].t]=e[j].t==mn[e[j].t]?f[i]:mn[e[j].t];
        }
        for(int i=1;i<=cnt;++i)id[i]=id[i]==sd[i]?id[i]:id[id[i]];
    }
}T;
ll ans[MN+5];
int main()
{
    int n,m,x,y,i;
    while(~scanf("%d%d",&n,&m))
    {
        memset(&T,0,sizeof(T));
        while(m--)x=read(),y=read(),T.ins(x,y);
        T.build(n);
        for(i=1;i<=T.cnt;++i)ans[i]=ans[T.id[i]]+T.p[i];
        for(i=1;i<=n;++i)printf("%I64d%c",ans[T.d[i]],i<n?' ':'
');
    }
}