hdu 4694 Important Sisters【支配树】

求出支配树输出到father的和即可

支配树见：https://blog.csdn.net/a710128/article/details/49913553

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

const int N=300005;

int n,m,h[N],cnt,se[N],id[N],rl[N],fa[N],dfn[N],tot,f[N],v[N];

long long ans[N];

vector<int>p[N],d[N];

struct qwe

{

	int ne,to;

}e[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void dfs(int u)

{

	dfn[u]=++tot;

	rl[tot]=u;

	for(int i=h[u];i;i=e[i].ne)

	{

		p[e[i].to].push_back(u);

		if(!dfn[e[i].to])

		{

			fa[e[i].to]=u;

			dfs(e[i].to);

		}

	}

}

int zhao(int x)

{

	if(f[x]==x)

		return x;

	int fa=zhao(f[x]);

	if(dfn[se[v[f[x]]]]<dfn[se[v[x]]])

		v[x]=v[f[x]];

	return f[x]=fa;

}

int main()

{

	while(~scanf("%d%d",&n,&m))

	{

		memset(h,0,sizeof(h));

		memset(id,0,sizeof(id));

		memset(dfn,0,sizeof(dfn));

		memset(ans,0,sizeof(ans));

		cnt=0;tot=0;

		for(int i=1;i<=n;i++)

			p[i].clear(),d[i].clear(),f[i]=v[i]=se[i]=i;

		for(int i=1;i<=m;i++)

		{

			int x=read(),y=read();

			add(x,y);

		}

		dfs(n);

		for(int i=tot;i>=2;i--)

		{

			for(int j=0;j<p[rl[i]].size();j++)

			{

				if(dfn[p[rl[i]][j]]<dfn[rl[i]])

					se[rl[i]]=(dfn[se[rl[i]]]<dfn[p[rl[i]][j]])?se[rl[i]]:p[rl[i]][j];

				else

				{

					zhao(p[rl[i]][j]);

					se[rl[i]]=(dfn[se[rl[i]]]<dfn[se[v[p[rl[i]][j]]]])?se[rl[i]]:se[v[p[rl[i]][j]]];

				}

			}

			f[rl[i]]=fa[rl[i]];

			d[se[rl[i]]].push_back(rl[i]);

			for(int j=0;j<d[fa[rl[i]]].size();j++)

			{

				zhao(d[fa[rl[i]]][j]);

				id[d[fa[rl[i]]][j]]=(dfn[se[v[d[fa[rl[i]]][j]]]]<dfn[se[d[fa[rl[i]]][j]]])?v[d[fa[rl[i]]][j]]:fa[rl[i]];

			}

		}

		for(int i=2;i<=tot;i++)

			if(id[rl[i]]!=se[rl[i]])

				id[rl[i]]=id[id[rl[i]]];

		for(int i=1;i<=n;i++)

			ans[i]=0;

		for(int i=1;i<=tot;i++)

		{

			ans[rl[i]]+=rl[i];

			if(id[rl[i]])

				ans[rl[i]]+=ans[id[rl[i]]];

		}

		for(int i=1;i<n;i++)

			printf("%lld ",ans[i]);

		printf("%lld\n",ans[n]);

	}

	return 0;

}