基准时间限制：1 秒 空间限制：131072 KB
给定一棵无根树，假设它有n个节点，节点编号从1到n, 求任意两点之间的距离（最短路径）之和。
Input
第一行包含一个正整数n (n <= 100000)，表示节点个数。
后面(n - 1)行，每行两个整数表示树的边。
Output
每行一个整数，第i(i = 1,2,...n)行表示所有节点到第i个点的距离之和。
Input示例
4
1 2
3 2
4 2
Output示例
5
3
5
5
思路：dp[i]表示以1为根，以i为子树的所有子节点到i的最短距离之和；
dfs遍历求dp数组，和以i为子树的节点数和si；
dfs2求总父亲节点来的价值；
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<time.h>
using namespace std;
#define LL long long
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e5+,M=1e6+,inf=1e9+,MOD=1e9+;
const LL INF=1e18+,mod=1e9+;
const double eps=(1e-),pi=(*atan(1.0)); struct is
{
int v,nex;
}edge[N<<];
int head[N],edg;
void add(int u,int v)
{
edge[++edg]=(is){v,head[u]};
head[u]=edg;
}
LL ans[N],a[N];
int si[N];
void dfs(int u,int fa)
{
si[u]=;
for(int i=head[u];i;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u);
si[u]+=si[v];
a[u]+=a[v]+si[v];
}
}
int n;
void dfs2(int u,int fa,LL now)
{
ans[u]=a[u]+now;
for(int i=head[u];i;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs2(v,u,now+a[u]-a[v]-si[v]+n-si[v]);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(,);
dfs2(,,);
for(int i=;i<=n;i++)
printf("%lld\n",ans[i]);
return ;
}