#if __INCLUDE_LEVEL__ == 0 #include __BASE_FILE__ int Op(int x, int y) { return max(x, y); } int E() { return -INF; } int Mapping(int f, int x) { return x + f; } int Composition(int g, int f) { return f + g; } int Id() { return 0; } void Solve() { int n; IN(n); HldTree g(n); for (int e : Rep(0, n - 1)) { int i, j; IN(i, j); --i, --j; g.add_edge({i, j, 1}); } g.build(0); vector tour; Fix([&](auto self, int i) -> void { tour.push_back(i); for (auto [j, e] : g.adj[i]) { if (e == g.pe[j]) { self(j); tour.push_back(i); } } })(0); tour.pop_back(); int N = 2 * n - 2; assert(Sz(tour) == N); vector pos_min(n, INF); vector pos_max(n, -INF); for (int t : Rep(0, N)) { int i = tour[t]; SetMin(pos_min[i], t); SetMax(pos_max[i], t); } atcoder::lazy_segtree seg(N + N); for (int t : Rep(0, N + N)) { int i = tour[t % N]; seg.set(t, g.depth[i]); } int64_t base = 0; vector> queries; vector memo(n - 1); Fix([&](auto self, int i) -> void { { int mx = seg.all_prod(); base += mx; int l = pos_min[i]; int x = seg.max_right(l, LAMBDA(x, x < mx)); x = tour[x % N]; int r = N + pos_min[i]; int y = seg.min_left(r, LAMBDA(x, x < mx)); y = tour[(y - 1) % N]; int j = g.lca(i, x) ^ g.lca(i, y) ^ g.lca(x, y); queries.emplace_back(i, j); } if (i) { int e = g.pe[i]; memo[e] = seg.prod(pos_min[i], pos_max[i] + 1); SetMax(memo[e], seg.prod(pos_max[i] + 1, N + pos_min[i]) - 1); } for (auto [j, e] : g.adj[i]) { if (e == g.pe[j]) { basic_string s; s += 0; s += pos_min[j]; s += pos_max[j] + 1; s += N + pos_min[j]; s += N + pos_max[j] + 1; s += N + N; for (int si : Rep(0, Sz(s) - 1)) { int l = s[si]; int r = s[si + 1]; seg.apply(l, r, si & 1 ? -1 : 1); } self(j); for (int si : Rep(0, Sz(s) - 1)) { int l = s[si]; int r = s[si + 1]; seg.apply(l, r, si & 1 ? 1 : -1); } } } })(0); vector f(n + 1); for (auto [i, j] : queries) { g.apply(i, j, false, [&](int l, int r) { if (l > r) { swap(l, r); } ++f[l]; --f[r]; }); } for (int i : Rep(0, n)) { f[i + 1] += f[i]; } for (int e : Rep(0, n - 1)) { int i = g.deeper(e); OUT(base - f[g.in[i]] - memo[e]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Solve(); } #elif __INCLUDE_LEVEL__ == 1 #include #include struct Graph { struct Edge { int src, dst; int64_t cost; int other(int v) const { __glibcxx_assert(v == src or v == dst); return src ^ dst ^ v; } }; std::vector edges; std::vector>> adj; Graph() {} explicit Graph(int n) : adj(n) {} int n() const { return std::size(adj); } int m() const { return std::size(edges); } int add_edge(const Edge& e, bool directed) { __glibcxx_assert(0 <= e.src and e.src < n()); __glibcxx_assert(0 <= e.dst and e.dst < n()); int id = m(); edges.push_back(e); adj[e.src].emplace_back(e.dst, id); if (not directed) adj[e.dst].emplace_back(e.src, id); return id; } }; struct DfsTree : Graph { using T = decltype(Edge::cost); std::vector root; std::vector pv; std::vector pe; std::vector order; std::vector in; std::vector out; std::vector sub; std::vector depth; std::vector min_depth; std::vector dist; std::vector last; int num_trials; DfsTree() {} explicit DfsTree(int n) : Graph(n), root(n, -1), pv(n, -1), pe(n, -1), in(n, -1), out(n, -1), sub(n, -1), depth(n, -1), min_depth(n, -1), dist(n, std::numeric_limits::max()), last(n, -1), num_trials(0) {} int add_edge(const Edge& e) { return Graph::add_edge(e, false); } void dfs(int r, bool clear_order = true) { __glibcxx_assert(0 <= r and r < n()); root[r] = r; pv[r] = -1; pe[r] = -1; if (clear_order) order.clear(); depth[r] = 0; dist[r] = T{}; dfs_impl(r); ++num_trials; } void dfs_all() { std::fill(std::begin(root), std::end(root), -1); for (int v = 0; v < n(); ++v) if (root[v] == -1) dfs(v, v == 0); } int deeper(int id) const { __glibcxx_assert(0 <= id and id < m()); int a = edges[id].src; int b = edges[id].dst; return depth[a] < depth[b] ? b : a; } bool is_tree_edge(int id) const { __glibcxx_assert(0 <= id and id < m()); return id == pe[deeper(id)]; } bool is_ancestor(int u, int v) const { __glibcxx_assert(0 <= u and u < n()); __glibcxx_assert(0 <= v and v < n()); return in[u] <= in[v] and out[v] <= out[u]; } private: void dfs_impl(int v) { in[v] = std::size(order); order.push_back(v); sub[v] = 1; min_depth[v] = depth[v]; last[v] = num_trials; for (auto&& [u, id] : adj[v]) { if (id == pe[v]) continue; if (last[u] == num_trials) { min_depth[v] = std::min(min_depth[v], depth[u]); continue; } root[u] = root[v]; pv[u] = v; pe[u] = id; depth[u] = depth[v] + 1; dist[u] = dist[v] + edges[id].cost; dfs_impl(u); sub[v] += sub[u]; min_depth[v] = std::min(min_depth[v], min_depth[u]); } out[v] = std::size(order); } }; struct HldTree : DfsTree { std::vector head; HldTree() {} explicit HldTree(int n) : DfsTree(n), head(n, -1) {} void build(int r, bool clear_order = true) { __glibcxx_assert(0 <= r and r < n()); dfs(r, clear_order); order.erase(std::end(order) - sub[r], std::end(order)); head[r] = r; build_impl(r); } void build_all() { std::fill(std::begin(root), std::end(root), -1); for (int v = 0; v < n(); ++v) if (root[v] == -1) build(v, v == 0); } int lca(int u, int v) const { __glibcxx_assert(0 <= u and u < n()); __glibcxx_assert(0 <= v and v < n()); __glibcxx_assert(root[u] == root[v]); while (true) { if (in[u] > in[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = pv[head[v]]; } } int d(int u, int v) const { __glibcxx_assert(0 <= u and u < n()); __glibcxx_assert(0 <= v and v < n()); __glibcxx_assert(root[u] == root[v]); return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } T distance(int u, int v) const { __glibcxx_assert(0 <= u and u < n()); __glibcxx_assert(0 <= v and v < n()); __glibcxx_assert(root[u] == root[v]); return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } int la(int v, int d) const { __glibcxx_assert(0 <= v and v < n()); __glibcxx_assert(0 <= d and d <= depth[v]); while (depth[head[v]] > d) v = pv[head[v]]; return order[in[head[v]] + (d - depth[head[v]])]; } int next(int src, int dst) const { __glibcxx_assert(0 <= src and src < n()); __glibcxx_assert(0 <= dst and dst < n()); __glibcxx_assert(root[src] == root[dst]); __glibcxx_assert(src != dst); if (not is_ancestor(src, dst)) return pv[src]; return la(dst, depth[src] + 1); } int next(int src, int dst, int k) const { __glibcxx_assert(0 <= src and src < n()); __glibcxx_assert(0 <= dst and dst < n()); __glibcxx_assert(root[src] == root[dst]); __glibcxx_assert(k >= 0); int v = lca(src, dst); if (k <= depth[src] - depth[v]) return la(src, depth[src] - k); k -= depth[src] - depth[v]; __glibcxx_assert(k <= depth[dst] - depth[v]); return la(dst, depth[v] + k); } template void apply(int src, int dst, bool vertex, Function f) const { __glibcxx_assert(0 <= src and src < n()); __glibcxx_assert(0 <= dst and dst < n()); __glibcxx_assert(root[src] == root[dst]); int v = lca(src, dst); while (head[src] != head[v]) { f(in[src] + 1, in[head[src]]); src = pv[head[src]]; } if (vertex) f(in[src] + 1, in[v]); else if (src != v) f(in[src] + 1, in[v] + 1); auto rec = [&](auto self, int to) -> void { if (head[v] == head[to]) { if (v != to) f(in[v] + 1, in[to] + 1); return; } self(self, pv[head[to]]); f(in[head[to]], in[to] + 1); }; rec(rec, dst); } template int search(int src, int dst, bool vertex, Searcher f) const { __glibcxx_assert(0 <= src and src < n()); __glibcxx_assert(0 <= dst and dst < n()); __glibcxx_assert(root[src] == root[dst]); int res = -1; apply(src, dst, vertex, [&](int l, int r) { if (res != -1) return; int i = f(l, r); if (l > r) std::swap(l, r); if (l <= i and i < r) res = vertex ? order[i] : pe[order[i]]; }); return res; } private: void build_impl(int v) { in[v] = std::size(order); order.push_back(v); auto pos = std::partition(std::begin(adj[v]), std::end(adj[v]), [&](auto&& e) { return e.second == pe[e.first]; }); auto it = std::max_element(std::begin(adj[v]), pos, [&](auto&& a, auto&& b) { return sub[a.first] < sub[b.first]; }); if (it != std::begin(adj[v])) std::iter_swap(std::begin(adj[v]), it); std::partition(pos, std::end(adj[v]), [&](auto&& e) { return e.second == pe[v]; }); for (auto&& [u, id] : adj[v]) { if (id != pe[u]) break; head[u] = u == adj[v].front().first ? head[v] : u; build_impl(u); } out[v] = std::size(order); } }; template class Fix { public: explicit Fix(F f) : f_(std::move(f)) {} template decltype(auto) operator()(Ts&&... xs) { return f_(std::ref(*this), std::forward(xs)...); } template decltype(auto) operator()(Ts&&... xs) const { return f_(std::ref(*this), std::forward(xs)...); } private: F f_; }; template concept MyRange = std::ranges::range && !std::convertible_to; template concept MyTuple = std::__is_tuple_like::value && !MyRange; namespace std { istream& operator>>(istream& is, MyRange auto&& r) { for (auto&& e : r) is >> e; return is; } istream& operator>>(istream& is, MyTuple auto&& t) { apply([&](auto&... xs) { (is >> ... >> xs); }, t); return is; } ostream& operator<<(ostream& os, MyRange auto&& r) { auto sep = ""; for (auto&& e : r) os << exchange(sep, " ") << e; return os; } ostream& operator<<(ostream& os, MyTuple auto&& t) { auto sep = ""; apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t); return os; } } // namespace std using namespace std; #define LAMBDA(x, ...) ([&](auto&& x) -> decltype(auto) { return __VA_ARGS__; }) #define LAMBDA2(x, y, ...) ([&](auto&& x, auto&& y) -> decltype(auto) { return __VA_ARGS__; }) #define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__) #define Sz(r) int(size(r)) #define SetMin(...) LAMBDA2(x, y, y < x && (x = y, 1))(__VA_ARGS__) #define SetMax(...) LAMBDA2(x, y, x < y && (x = y, 1))(__VA_ARGS__) #define INF (INT_MAX / 2) #define IN(...) (cin >> forward_as_tuple(__VA_ARGS__)) #define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n') #endif // __INCLUDE_LEVEL__ == 1