基准时间限制：1 秒 空间限制：131072 KB 分值: 40
难度：4级算法题
收藏
关注
给定一棵无根树，假设它有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
思路：
首先，任选一个节点，设定为树的根。
用num[x]表示以节点x为根的子树的节点总数(包含x自身)
假如设定节点1为根，则先求出dp[1]，表示所有节点到节点1的距离之和，
对根而言也是所有节点的深度之和。
若x是y的子结点，则有
dp[x] = dp[y] + (n-num[x]) - num[x];
因为x为根的子树的所有节点到x的距离比到y的距离少1，所以减num[x]
其余节点到x的距离比到y的距离多1，所以加 n-num[x]
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#pragma comment(linker, "/STACK:10240000,10240000")//递归太深，导致爆栈，所以使用扩栈语句
using namespace std;
const int N = 100009;
int dp[N] = {}, num[N];
vector<int> p[N];
bool f[N] = {};
void dfs(int s, int depth)
{
int len = p[s].size();
f[s] = 1;
num[s] = 1;
dp[1] += depth;
for(int i=0; i<len; i++)
{
if(!f[p[s][i]])
{
dfs(p[s][i], depth+1);
num[s] += num[p[s][i]];
}
}
}
void solve(int s, int n)
{
int len = p[s].size();
f[s] = 1;
for(int i=0; i<len; i++)
{
if(!f[p[s][i]])
{
dp[p[s][i]] = dp[s]+n-num[p[s][i]]*2;
solve(p[s][i], n);
}
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
p[a].push_back(b);
p[b].push_back(a);
}
dfs(1, 0);
memset(f, 0, sizeof(f));
solve(1, n);
for(int i=1; i<=n; i++)
printf("%d\n", dp[i]);
return 0;
}