#include // clang-format off using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{template string f(T i){string s=(i==INF||i==INFll?"inf":to_string(i));s=string(max(0,3-int(s.size())),' ')+s;return s;} templateauto v(T&x,string end)->decltype(cerr<void v(const pair&p,string end="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+end);}templatevoid v(const tuple&t,string end="\n"){auto[a,b]=t;cerr<<"(";v(a,", ");v(b,")"+end);}templatevoid v(const tuple&t,string end="\n"){auto[a,b,c]=t;cerr<<"(";v(a,", ");v(b,", ");v(c,")"+end);}templatevoid v(const tuple&t,string end="\n"){auto[a,b,c,d]=t;cerr<<"(";v(a,", ");v(b,", ");v(c,", ");v(d,")"+end);} templatevoid v(const vector&vx,string);templateauto ve(int,const vector&vx)->decltype(cerr<auto ve(bool,const vector &vx){cerr << "{\n";for(const T&x:vx)cerr<<" ",v(x,",");cerr<<"}\n";}templatevoid v(const vector&vx, string){ve(0,vx);}templatevoid v(const deque&s,string e){vectorz(s.begin(),s.end());v(z,e);} templatevoid v(const set&s,string e){vectorz(s.begin(),s.end());v(z,e);}templatevoid v(const multiset&s,string e){vectorz(s.begin(),s.end());v(z,e);}templatevoid v(const unordered_set&s,string e){vectorz(s.begin(),s.end());v(z,e);}templatevoid v(const priority_queue&p,string e){priority_queueq=p;vectorz;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);} templatevoid v(const map&m,string e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<" [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;}templatevoid _view(int n,string s,T&var){cerr<<"\033[1;32m"<void grid(T _){}void grid(const vector>&vvb){cerr<<"\n";for(const vector&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}} void _debug(int,string){}templatevoid _debug(int n,string S,H h,T... t){int i=0,cnt=0;for(;iap;mint re=a;for(long long r=1;r struct Rerooting { Rerooting(vector>> &adj) { g = adj; }; void build() { memo.resize(g.size(), e()); dp.resize(g.size()); dfs1(0, -1); dfs2(0, -1, e()); } S const query(int idx) { return dp[idx]; } private: vector dp, memo; vector>> g; void dfs1(int v, int p) { bool update = false; for (auto &[nv, w] : g[v]) { if (nv == p) continue; dfs1(nv, v); update = true; memo[v] = merge(memo[v], apply(memo[nv], nv, v, w)); } if (!update) memo[v] = leaf(); } void dfs2(int v, int p, const S &val) { vector ds{val}; for (auto &[nv, w] : g[v]) { if (nv == p) continue; ds.push_back(apply(memo[nv], nv, v, w)); } // この時点のdsには、各頂点における部分木のdpの値が入っている。 int n = ds.size(), idx = 1; vector left(n + 1, e()), right(n + 1, e()); for (int i = 0; i++ < n;) left[i] = merge(left[i - 1], ds[i - 1]); for (int i = n; i-- > 0;) right[i] = merge(right[i + 1], ds[i]); dp[v] = left[n]; for (auto &[nv, w] : g[v]) { if (nv == p) continue; S sub = merge(left[idx], right[idx + 1]); dfs2(nv, v, apply(sub, v, nv, w)); idx++; } } }; using S = long long; // dpの値の型 using T = int; // 辺の重みの型 S merge(S a, S b) { return a + b; } // モノイドの二項演算 S e() { return 0; } // モノイドの単位元 S leaf() { return 0; } // 葉のdpの値 S apply(S dpv, int v, int p, T w) { // (子のdp,子,親,重み) 親に返す値 return dpv + (v > p ? 0 : 1); } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector>> adj(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].emplace_back(v, 1); adj[v].emplace_back(u, 1); } Rerooting g(adj); g.build(); for (int i = 0; i < N; i++) { cout << g.query(i) << endl; } return 0; }