给定一棵无根树，假设它有n个节点，节点编号从1到n, 求1-n这n个节点，到其他n-1个节点的距离之和。
Input 第一行包含一个正整数n (n <= 100000)，表示节点个数。 后面(n - 1)行，每行两个整数表示树的边。 Output 每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。 Sample Input 4 1 2 3 2 4 2 Sample Output 5 3 5 5
思路： 换根dp。 第一次扫描得出节点1的值。 第二次扫描加上父节点的距离值，得到每个节点为根的值。
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; int siz[maxn],res[maxn]; int head[maxn],nex[maxn * 2],to[maxn * 2],tot; ll f[maxn]; int n; void add(int x,int y) { to[++tot] = y; nex[tot] = head[x]; head[x] = tot; } void dfs(int u,int fa) { siz[u] = 1; for(int i = head[u];i;i = nex[i]) { int v = to[i]; if(v == fa) continue; dfs(v,u); siz[u] += siz[v]; f[u] += siz[v] + f[v]; } } void dfs2(int u,int fa) { for(int i = head[u];i;i = nex[i]) { int v = to[i]; if(v == fa) continue; ll num = f[u] - siz[v] - f[v]; f[v] += (n - siz[v]) + num; dfs2(v,u); } } int main() { scanf("%d",&n); for(int i = 1;i < n;i++) { int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(1,-1); dfs2(1,-1); for(int i = 1;i <= n;i++) { printf("%lld\n",f[i]); } return 0; }