支配树模板

#include
     
      #include
      
       #include
       
        using namespace std;#define ll long longinline 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 100000struct 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]]]
        
         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