#include #include using namespace std; using isize = size_t; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using f64 = long double; using p2 = pair; using el = tuple; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(18); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) res *= t; t *= t; n >>= 1; } return res; } i64 n; vector g[200000]; p2 par[200000]; i64 dep[200000]; p2 dp[200000]; p2 dps[200000]; vector et; i64 idx[200000]; i64 ispar[200000]; void dfs(i64 v) { dp[v] = {0, v}; idx[v] = et.size(); et.push_back(v); for (auto [nv, id] : g[v]) { if (par[v].first == nv) continue; par[nv] = {v, id}; dep[nv] = dep[v] + 1; dfs(nv); et.push_back(v); if (dp[v].first < dp[nv].first + 1) { dp[v] = {dp[nv].first + 1, dp[nv].second}; ispar[v] = nv; } else if (dp[v].first == dp[nv].first + 1) { dp[v].second = v; ispar[v] = -1; } } } vector out; i64 sum = 0; void dfs1(i64 v, p2 mxp) { if (mxp.first < 0) { mxp = {0, v}; } else if (mxp.first == 0) { mxp.second = v; } vector V = {{0, v, v}}; V.push_back({mxp.first, mxp.second, mxp.second}); for (auto [nv, id] : g[v]) { if (nv != par[v].first) { V.push_back({dp[nv].first + 1, dp[nv].second, nv}); } } sort(V.begin(), V.end()); reverse(V.begin(), V.end()); dps[v] = {get<0>(V[0]), get<1>(V[0])}; if (get<0>(V[0]) == get<0>(V[1])) ispar[v] = -1, dps[v].second = v; else ispar[v] = get<2>(V[0]), dps[v].second = get<1>(V[0]); for (auto [nv, id] : g[v]) { if (par[v].first == nv) continue; if (get<2>(V[0]) == nv) { assert(V.size() >= 3); if (get<0>(V[1]) != get<0>(V[2])) { dfs1(nv, {get<0>(V[1]) + 1, get<1>(V[1])}); } else { dfs1(nv, {get<0>(V[1]) + 1, v}); } } else { if (get<0>(V[0]) != get<0>(V[1])) { dfs1(nv, {get<0>(V[0]) + 1, get<1>(V[0])}); } else { dfs1(nv, {get<0>(V[0]) + 1, v}); } } } sum += dps[v].first; out.push_back({v, dps[v].second}); } i64 cnt[200000]; i64 ans[200000]; void dfs2(i64 v) { for (auto [nv, id] : g[v]) { if (par[v].first == nv) continue; dfs2(nv); cnt[v] += cnt[nv]; } if (par[v].second != -1) { ans[par[v].second] = sum + cnt[v] - dps[par[v].first].first - dps[v].first; if (ispar[par[v].first] == v) ans[par[v].second]++; if (ispar[v] == par[v].first) ans[par[v].second]++; ans[par[v].second] += dps[v].first; if (ispar[v] == par[v].first) ans[par[v].second]--; } } p2 op(p2 a, p2 b){return min(a, b);} p2 e() {return {1e18, 1e18};} void _main() { cin >> n; for (i64 i = 0; i < n - 1; i++) { i64 u, v; cin >> u >> v; u--, v--; g[u].push_back({v, i}); g[v].push_back({u, i}); } dep[0] = 0; par[0] = {-1, -1}; dfs(0); dfs1(0, {-1e18, -1e18}); atcoder::segtree seg(et.size()); for (i64 i = 0; i < et.size(); i++) { seg.set(i, {dep[et[i]], et[i]}); } for (auto [a, b] : out) { if (a == b) continue; if (idx[a] > idx[b]) swap(a, b); i64 lca = seg.prod(idx[a], idx[b] + 1).second; if (lca == a) { cnt[a]++; cnt[b]--; } else { cnt[a]--, cnt[b]--; cnt[lca] += 2; } } cout << "\n"; dfs2(0); for (i64 i = 0; i < n - 1; i++) { cout << ans[i] << "\n"; } }