501 距离和

itdef / 2024-10-11 / 原文

// 501 距离和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*

http://oj.daimayuan.top/course/5/problem/224

有一棵 n个节点的树，节点编号从 1到 n。
请求出每个节点到其他所有节点的距离的和。

定义两个节点的距离为它们之间的简单路径上经过了多少条边。

输入格式
第一行一个整数 n表示节点数。

接下来 n−1行，每行两个整数 x,y表示 x号节点和 y号节点之间有一条边。


数据保证读入的是一棵树。

输出格式
输出共 n行，第 i行一个整数表示 i号节点到其他所有节点的距离的和。

样例输入
5
1 2
1 5
2 3
2 4
样例输出
6
5
8
8
9
数据规模
对于所有数据，保证 2≤n≤105,1≤x,y≤n。
*/


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>

using namespace std;

const int N = 100010;
long long dp[N], v[N], cnt[N];
int h[N], e[N*2], ne[N*2], idx;
int n;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void down(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        down(j, u);
        dp[u] += dp[j];
        cnt[u] += cnt[j];
    }
    dp[u] += cnt[u];
    cnt[u]++;
}

void up(int u, int fa) {
    if (fa != -1) {
        v[u] = v[fa] + dp[fa] - dp[u] - cnt[u] + n - cnt[u];
    }
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        up(j, u);
    }
}


int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b; cin >> a >> b;
        add(a, b); add(b, a);
    }

    down(1, -1);
    up(1, -1); 

    for (int i = 1; i <= n; i++) {
        cout << dp[i] + v[i] << endl;
    }
    
    return 0;
}