#include #include "atcoder/dsu" using i64 = std::int64_t; struct TreeManager { int n, lg; std::vector> tree; std::vector in, out, par, depth; std::vector> table; TreeManager(const std::vector> &tree_) { tree = tree_; n = (int)tree.size(); lg = 0; while ((1 << lg) < n) ++lg; int id = 0; in.assign(n, 0); out.assign(n, 0); par.assign(n, 0); depth.assign(n, 0); dfs(0, -1, 0, id); constructTable(); } void dfs(const int v, const int p, const int d, int &id) { in[v] = id++; depth[v] = d; par[v] = p; for (const int t : tree[v]) { if (t == p) continue; dfs(t, v, d + 1, id); } out[v] = id++; } void constructTable() { table.resize(lg); table[0] = par; for (int rank = 1; rank < lg; ++rank) { table[rank].assign(n, -1); for (int i = 0; i < n; ++i) { const int t1 = table[rank - 1][i]; if (t1 == -1) table[rank][i] = -1; else table[rank][i] = table[rank - 1][t1]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) std::swap(u, v); for (int rank = lg - 1; rank >= 0; --rank) { const int p = table[rank][v]; if (p != -1 and depth[p] >= depth[u]) v = p; } assert(depth[u] == depth[v]); if (u == v) return u; for (int rank = lg - 1; rank >= 0; --rank) { const int a = table[rank][u], b = table[rank][v]; if (a != b) { u = a; v = b; } } return par[u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } }; struct FenwickTree { int n; std::vector data; FenwickTree(int n_) : n(n_), data(n + 1, 0) {} void add(int i, i64 v) { ++i; while (i <= n) { data[i] += v; i += i & -i; } } i64 fold(int r) { i64 ret = 0; while (r != 0) { ret += data[r]; r -= r & -r; } return ret; } i64 fold(int l, int r) { return fold(r) - fold(l); } }; std::vector main_(std::vector, std::vector); std::vector naive_(std::vector, std::vector); void randomTest() { static constexpr int N = 1000; std::mt19937 mt; std::uniform_int_distribution dist(0, N - 1); int tests = 100; while (tests--) { std::vector X, Y; int cnt = 0; atcoder::dsu uft(N); while (cnt != N - 1) { const int a = dist(mt), b = dist(mt); if (uft.same(a, b)) continue; uft.merge(a, b); X.push_back(a); Y.push_back(b); ++cnt; } const auto ans = naive_(X, Y), challanger = main_(X, Y); if (ans != challanger) { std::cout << "Id : " << tests << std::endl; std::cout << N << std::endl; for (int i = 0; i < N - 1; ++i) { std::cout << X[i] << ' ' << Y[i] << std::endl; } for (const auto e : challanger) std::cout << e << ' '; std::cout << std::endl; for (const auto e : ans) std::cout << e << ' '; std::cout << std::endl << std::endl; } } } int main() { // randomTest(); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N; std::cin >> N; std::vector X(N - 1), Y(N - 1); for (int i = 0; i < N - 1; ++i) { std::cin >> X[i] >> Y[i]; --X[i], --Y[i]; } const auto ans = main_(X, Y); for (const auto e : ans) { std::cout << e << std::endl; } } std::vector main_(std::vector X, std::vector Y) { const int N = (int)X.size() + 1; std::vector> Tree(N); for (int i = 0; i < N - 1; ++i) { Tree[X[i]].push_back(Y[i]); Tree[Y[i]].push_back(X[i]); } TreeManager sTree(Tree); std::vector distList(N); for (int i = 1; i < N; ++i){ distList[i] = sTree.dist(i - 1, i); } FenwickTree fenTree1(N), fenTree2(N); std::vector isAvailable(N, true); std::vector subSize(N); std::vector dist1(N, -1), dist2(N, -1); std::vector ans(N); auto decomposite = [&](auto &&selfD, const int root) -> void { auto dfs1 = [&](auto &&self, const int v, const int p) -> int { subSize[v] = 1; dist1[v] = dist2[v] = -1; for (const int t : Tree[v]) { if (t == p) continue; if (not isAvailable[t]) continue; subSize[v] += self(self, t, v); } return subSize[v]; }; dfs1(dfs1, root, -1); const int s = subSize[root]; auto dfs2 = [&](auto &&self, const int v, const int p) -> int { bool isCentroid = true; int ret = -1; for (const int t : Tree[v]) { if (t == p) continue; if (not isAvailable[t]) continue; const int res = self(self, t, v); if (res != -1) return res; if (subSize[t] > s / 2) isCentroid = false; } if (s - subSize[v] > s / 2) isCentroid = false; if (isCentroid) ret = v; return ret; }; const int centroid = dfs2(dfs2, root, -1); std::vector> qs; dist1[centroid] = 0; for (const int t : Tree[centroid]) { if (not isAvailable[t]) continue; std::vector> qsc; auto dfs3 = [&](auto &&self, const int v, const int p, const int d) -> void { const int d1 = distList[v]; if (d1 - 1 >= d) qsc.push_back({d1 - 1 - d, v}); for (const int t : Tree[v]) { if (t == p) continue; if (not isAvailable[t]) continue; self(self, t, v, d + 1); } }; dfs3(dfs3, t, centroid, 1); std::sort(qsc.begin(), qsc.end(), [](const auto &a, const auto &b) { return a.first < b.first; }); std::queue que; que.push(t); dist1[t] = 1; for (const auto &[a, i] : qsc) { fenTree1.add(i, a); fenTree2.add(i, 1); } int r = 0; while (not que.empty()) { const auto f = que.front(); que.pop(); while (r != (int)qsc.size() and qsc[r].first - dist1[f] <= 0) { fenTree1.add(qsc[r].second, -qsc[r].first); fenTree2.add(qsc[r].second, -1); ++r; } ans[f] -= fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist1[f]; for (const int to : Tree[f]) { if (not isAvailable[to]) continue; if (dist1[to] != -1) continue; dist1[to] = dist1[f] + 1; que.push(to); } } while (r != (int)qsc.size()) { fenTree1.add(qsc[r].second, -qsc[r].first); fenTree2.add(qsc[r].second, -1); ++r; } std::copy(qsc.begin(), qsc.end(), std::back_inserter(qs)); } qs.push_back({distList[centroid] - 1, centroid}); std::sort(qs.begin(), qs.end(), [](const auto &a, const auto &b) { return a.first < b.first; }); std::queue que; que.push(centroid); dist2[centroid] = 0; for (const auto &[a, i] : qs) { fenTree1.add(i, a); fenTree2.add(i, 1); } int r = 0; while (not que.empty()) { const auto f = que.front(); que.pop(); while (r != (int)qs.size() and qs[r].first - dist2[f] <= 0) { fenTree1.add(qs[r].second, -qs[r].first); fenTree2.add(qs[r].second, -1); ++r; } ans[f] += fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist2[f]; for (const int to : Tree[f]) { if (not isAvailable[to]) continue; if (dist2[to] != -1) continue; dist2[to] = dist2[f] + 1; que.push(to); } } while (r != (int)qs.size()) { fenTree1.add(qs[r].second, -qs[r].first); fenTree2.add(qs[r].second, -1); ++r; } isAvailable[centroid] = false; for (const int t : Tree[centroid]) { if (not isAvailable[t]) continue; selfD(selfD, t); } }; decomposite(decomposite, 0); const auto baseAns = std::accumulate(distList.begin(), distList.end(), 0ll); for (auto &e : ans) e = baseAns - e; return ans; } std::vector naive_(std::vector X, std::vector Y) { const int N = (int)X.size() + 1; std::vector> Tree(N); for (int i = 0; i < N - 1; ++i) { Tree[X[i]].push_back(Y[i]); Tree[Y[i]].push_back(X[i]); } TreeManager sTree(Tree); std::vector ans(N); for (int i = 0; i < N; ++i) { for (int j = 1; j <= i; ++j) { ans[i] += sTree.dist(j - 1, j); } for (int j = i + 1; j < N; ++j) { const int a = sTree.dist(j - 1, j), b = sTree.dist(i, j) + 1; ans[i] += std::min(a, b); } } return ans; }