#include #include #include using namespace std; vector get_distance(const vector> &g, int start) { int n = g.size(); vector dist(n); auto dfs = [&] (auto rec, int x, int p) -> void { for (int y : g[x]) if (y != p) { dist[y] = dist[x] + 1; rec(rec, y, x); } }; dfs(dfs, start, -1); return dist; } // (diameter, center1, [center2]) tuple get_center(const vector> &g) { int n = g.size(); vector dist = get_distance(g, 0); int max_dist = -1, argmax = -1; for (int i = 0; i < n; i++) if (max_dist < dist[i]) max_dist = dist[i], argmax = i; dist = get_distance(g, argmax); max_dist = argmax = -1; for (int i = 0; i < n; i++) if (max_dist < dist[i]) max_dist = dist[i], argmax = i; vector pre(n, -1); for (int i = 0; i < n; i++) { for (int j : g[i]) if (dist[j] == dist[i] - 1) pre[i] = j; } vector path; int cur = argmax; while (cur != -1) { path.emplace_back(cur); cur = pre[cur]; } if (max_dist % 2) return {max_dist, path[max_dist/2], path[max_dist/2+1]}; else return {max_dist, path[max_dist/2], -1}; } int main() { int n; cin >> n; vector> g(n); vector> edge(n-1); for (int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); edge[i] = {u, v}; } auto [diameter, center1, center2] = get_center(g); int half = diameter / 2; vector dep(n), sz(n), cnt(n), top(n); auto dfs = [&] (auto rec, int u, int p, int dep_cur, int top_cur) -> void { dep[u] = dep_cur; top[u] = top_cur; sz[u] = 1; if (dep[u] == half) cnt[u] = 1; for (int v : g[u]) if (v != p) { rec(rec, v, u, dep_cur + 1, top_cur); cnt[u] += cnt[v]; sz[u] += sz[v]; } }; long long ans_before = 0; vector ans(n-1); if (diameter == half * 2) { int occur_half = 0, sum_sz = 0; for (int r : g[center1]) { dfs(dfs, r, center1, 1, r); if (cnt[r] > 0) occur_half++, sum_sz += sz[r]; } for (int i = 0; i < n; i++) ans_before += dep[i] + half; for (int i = 0; i < n-1; i++) { auto [u, v] = edge[i]; if (dep[u] > dep[v]) swap(u, v); ans[i] = ans_before; ans[i] -= dep[u] + half; ans[i] -= sz[v]; if (/*occur_half == 2 and */cnt[top[v]] > 0 and cnt[top[v]] == cnt[v]) { ans[i] -= sum_sz - sz[top[v]]; } } } else { dfs(dfs, center1, center2, 0, center1); dfs(dfs, center2, center1, 0, center2); for (int i = 0; i < n; i++) ans_before += dep[i] + half + 1; for (int i = 0; i < n-1; i++) { auto [u, v] = edge[i]; ans[i] = ans_before; if ((u == center1 and v == center2) or (u == center2 and v == center1)) { ans[i] -= half + n; } else{ if (dep[u] > dep[v]) swap(u, v); ans[i] -= dep[u] + half + 1; ans[i] -= sz[v]; if (cnt[top[v]] == cnt[v]) { ans[i] -= n - sz[top[v]]; } } } } for (int i = 0; i < n-1; i++) cout << ans[i] << "\n"; }