#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using ld = long double; using vl = vector; template using vc = vector; template using vvc = vector>; #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rep(i, n) for (ll i = 0; i < (n); i++) #define repr(i, n) for (ll i = (n)-1; i >= 0; i--) #define repe(i, l, r) for (ll i = (l); i < (r); i++) #define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--) #define repa(i,n) for (auto& i: n) template inline bool chmax(T1 &a, const T2 &b) {if (a inline bool chmin(T1 &a, const T2 &b) {if (b void verr(const set &st) { repa(a, st) cerr << a << " "; cerr << endl; } template void verr(const map &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; } template void verr(const vector>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; } template void verr(const vector& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; } ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; } template void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward(t)...); } #endif const ll INF = 4e18; const ld EPS = 1e-11; const ld PI = acos(-1.0L); // const ll MOD = 1e9 + 7; const ll MOD = 998244353; //--------------------------------------------------------------------------------// template< class V, class E > struct ReRooting{ private: struct edge{ ll to; E val; ll rev; // G[to]におけるfromのindex edge(){} edge(ll t_, E v_, ll r_): to(t_), val(v_), rev(r_){} }; ll N; vector> G; // グラフ vector res; // 各頂点を根としたときの値 vector> dp; vector> dpused; vector resused; V vid; E eid; public: ReRooting(ll N_, V vid_, E eid_) : N(N_), G(N_), res(N_, vid_), resused(N_), dp(N_), dpused(N_), vid(vid_), eid(eid_) {} void add_edge(ll a, ll b, E c){ G[a].emplace_back(b, c, G[b].size()); G[b].emplace_back(a, c, G[a].size() - 1); } // 頂点iのDataを取得 V get(ll i){ return res[i]; } void build(vector vVals, vector vids){ for (int i = 0; i < N; i++) dpused[i].resize(G[i].size(), false), dp[i].resize(G[i].size()); auto dfs = [&](auto&& dfs, ll now, ll paridx, bool flag) -> V { if (paridx != -1 and dpused[now][paridx]) return dp[now][paridx]; else if (paridx == -1 and resused[now]) return res[now]; // nowが全体の根、または初めの木DPのとき if (paridx == -1 or flag) { vector A; for (ll i = 0; i < G[now].size(); i++) { if (i == paridx) continue; A.emplace_back(rooting(dfs(dfs, G[now][i].to, G[now][i].rev, flag), G[now][i].val)); } // 右からの部分木の累積値 vector R = vector(N, vids[now]); for (ll i = A.size(); i > 0; i--) R[i - 1] = accumul(R[i], A[i - 1]); if (paridx == -1) { V L = vids[now]; for (ll i = 0; i < G[now].size(); i++) { dpused[now][i] = true; dp[now][i] = apply(merge(L, R[i + 1]), vVals[now]); //now->to方向の部分木を除いた値 // 左から部分木を累積 L = accumul(L, A[i]); } } if (paridx == -1) { resused[now] = true; return res[now] = apply_root(R[0], vVals[now]); } else { dpused[now][paridx] = true; return dp[now][paridx] = apply(R[0], vVals[now]); } } // 2回目のdfsで各頂点を根とするとき else { dfs(dfs, now, -1, flag); return dfs(dfs, now, paridx, flag); } }; dfs(dfs, 0, -1, true); for (ll i = 0; i < N; i++) dfs(dfs, i, -1, false); } }; // 頂点の型 struct vData { ll v, size, index; // size: 部分木の大きさ }; // 頂点データの単位元 vData vid = {0, 0, 0}; // 辺の型 struct eData { ll v1, v2; }; // 辺データの単位元 eData eid = {0, 0}; // 累積値に部分木情報を追加 vData accumul(vData acc, vData b){ acc.v += b.v, acc.size += b.size; return acc; }; // 左からの部分木の累積と右からの累積をマージ vData merge(vData a, vData b){ a.v += b.v, a.size += b.size; return a; } // 1つの部分木情報に辺を適用 vData rooting(vData a, eData e){ if(a.index == e.v1) { // err("eq", a.index, e.v2); if(a.index < e.v2) a.v++; }else{ // err("nt", a.index, e.v1); if (a.index < e.v1) a.v++; } // a.v += e.v; return a; } // マージし終えた頂点で計算 // 1. 根について全ての部分木をマージした後, 各頂点のデータを適用 vData apply_root(vData a, vData f){ a.size++; return a; // ここで部分木のサイズは増える } // 2. 根ではない頂点について1つの部分木を除いてマージした後 の2通りに適用 vData apply(vData a, vData f){ a.size++; return a; // ここで部分木のサイズは増える } // ReRooting R(N, vid, eid); // G.build(D); // D: vector 頂点ごとのデータ // G.get(i) // 頂点iのvDataを取得 int main() { ll N; cin >> N; ReRooting R(N, vid, eid); rep(i, N - 1) { ll a, b; cin >> a >> b, a--, b--; R.add_edge(a, b, {a, b}); } vc ds(N, vid); rep(i, N) ds[i] = {0, 0, i}; R.build(vc(N, vid), ds); rep(i, N) cout << R.get(i).v << '\n'; }