http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1405
题意:
思路:
先求出所有点到根节点的距离,需要维护每棵子树的大小,然后就可以再来一次dfs依次求出别的点的距离。好像需要手动扩栈。
#pragma comment(linker, "/STACK:10240000,10240000")
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = +;
const int inf = 0x3f3f3f3f; int n;
int num[maxn];
long long d[maxn];
vector<int> G[maxn]; void dfs(int u, int fa, int dep)
{
num[u] = ;
d[] += dep;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(v==fa) continue;
dfs(v,u,dep+);
num[u] += num[v];
}
} void dfs2(int u, int fa)
{
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(v==fa) continue;
d[v] = d[u]+n-num[v]-num[v];
dfs2(v,u);
}
} int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
d[] = ;
dfs(,,);
dfs2(,);
for(int i=;i<=n;i++) printf("%lld\n",d[i]);
return ;
}