Problem statement: https://atcoder.jp/contests/abc479/tasks/abc479_e

The goal of this blog is to present a solution different using an approach different from that of the official editorial.

Consider the centroid $$$c$$$ of the tree. For any cut, we know that the bigger component always contains $$$c$$$. For any vertex $$$v$$$, the only cuts that would result in $$$v$$$ being in the smaller component would be the cuts on the path between $$$c$$$ and $$$v$$$. So $$$x_v$$$ is simply the sum of all edge weights (which is $$$\frac{n(n-1)}{2}$$$) minus the distance from $$$c$$$ to $$$v$$$.

Below is an implementation that uses this idea.

#include<bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> t;
vector<int> sz;

int n;
int centroid;

void dfs_centroid(int u, int p) {
    sz[u] = 1;
    bool has_big_child = 0;

    for (auto & [v, i] : t[u]) {
        if (v == p) continue;
        dfs_centroid(v, u);
        if (2 * sz[v] > n) has_big_child = 1;
        sz[u] += sz[v];
    }

    if (!has_big_child and 2*sz[u] > n) centroid = u;
}

vector<long long> ans;

void dfs_ans(int u, int p, long long d) {
    ans[u] = 1LL * n * (n-1) / 2 - d;

    for (auto [v, i] : t[u]) {
        if (v == p) continue;
        dfs_ans(v, u, d+i);
    }
}

int main() {
    cin >> n;

    t.resize(n);
    sz.resize(n);

    for (int i = 1; i != n; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        t[a].push_back({b, i});
        t[b].push_back({a, i});
    }

    dfs_centroid(0, -1);
    
    ans.resize(n);
    dfs_ans(centroid, -1, 0);

    for (auto x : ans) cout << x << ' ';
    cout << '\n';
}