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 $u$ and $v$.↵
So $x_v$ is simply the sum of all edge weights (which is $\frac{n(n-1)}{2}$) minus the distance from $uc$ 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';↵
}↵
~~~~~↵
↵
↵
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 $u$ and $v$.↵
So $x_v$ is simply the sum of all edge weights (which is $\frac{n(n-1)}{2}$) minus the distance from $
↵
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';↵
}↵
~~~~~↵
↵
