给定一棵无根树，假设它有n个节点，节点编号从1到n, 求任意两点之间的距离（最短路径）之和。
输入
第一行包含一个正整数n (n <= 100000)，表示节点个数。
后面(n - 1)行，每行两个整数表示树的边。
输出
每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。
输入样例
4
1 2
3 2
4 2
输出样例
5
3
5
5
先选定节点1作为树的根，然后用num[i]表示以节点i为根的子树上的节点数（包括i）。
dp[x]表示节点x到其他所有节点距离之和，设节点x是节点xx的父节点。
那么我们可以得到dp[xx] = dp[x] + (n-num[xx]） - num[xx]。
因为在xx子树上的节点到xx的距离要比到父节点x的距离要少1，所以减去1，一共有num[xx]个，所以减去num[xx]
不在xx子树上的节点到xx的距离要比到父节点x的距离要多1，所以加上n - num[xx]。
这样我们首先一个dfs处理出dp[1]的大小，就可以推出其他的大小。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; int n; ll dp[maxn]; int vis[maxn], num[maxn]; vector<int> e[maxn]; void dfs(int x, int s) { vis[x] = 1; num[x] = 1; dp[1] += s; for (int i = 0; i < e[x].size(); i++) { int xx = e[x][i]; if (vis[xx] == 0) { dfs(xx, s + 1); num[x] += num[xx]; } } } void init_dp(int x) { vis[x] = 1; for (int i = 0; i < e[x].size(); i++) { int xx = e[x][i]; if (vis[xx] == 0) { dp[xx] = dp[x] + (n - num[xx]) - num[xx]; init_dp(xx); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int u, v; for (int i = 1; i <= n - 1; i++) { cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dp[1] = 0; memset(vis, 0, sizeof(vis)); dfs(1, 0); memset(vis, 0, sizeof(vis)); init_dp(1); for (int i = 1; i <= n; i++) { cout << dp[i] << endl; } return 0; }
