12817번: 버스 노선

https://www.acmicpc.net/problem/12817


$O(n)$

아무 노드 하나를 루트로 하는 rooted tree를 만든다.
r[i]: i번 버스 정류장에 멈추는 버스의 수
aj: i번 노드의 j(<=m)번째 자식의 자손 수
sj=sum(a[1...j])

r[i]={sum((sj+1)*a[j])+(sm+1)*(n-sm-1)}*2 이다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e6;
typedef long long ll;
int n;
vector<int> adj[MXN + 1];
ll r[MXN + 1];
int f(int h, int p) {
    ll s = 1;
    for (auto it : adj[h]) if (it^p) {
        int t = f(it, h);
        r[h] += s*t;
        s += t;
    }
    r[h] += s*(n - s);
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i<n - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    for (int i = 1; i <= n; i++) printf("%lld\n", r[i] * 2);
    return 0;
}