#include using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair P; typedef vector vec; using Graph = vector>; const long long INF = 1LL<<60; const long long MOD = 1000000007; //https://nyaannyaan.github.io/library/graph/graph-template.hpp template struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template Edges esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template vector> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector> d(N, vector(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ //https://nyaannyaan.github.io/library/tree/rerooting.hpp // Rerooting // f1(c1, c2) ... merge value of child node // f2(memo[i], chd, par) ... return value from child node to parent node // memo[i] ... result of subtree rooted i // dp[i] ... result of tree rooted i template struct Rerooting { const G &g; const F1 f1; const F2 f2; vector memo, dp; T I; Rerooting(const G &_g, const F1 _f1, const F2 _f2, const T &I_) : g(_g), f1(_f1), f2(_f2), memo(g.size(), I_), dp(g.size(), I_), I(I_) { dfs(0, -1); efs(0, -1, I); } const T &operator[](int i) const { return dp[i]; } void dfs(int cur, int par) { for (auto &dst : g[cur]) { if (dst == par) continue; dfs(dst, cur); memo[cur] = f1(memo[cur], f2(memo[dst], dst, cur)); } } void efs(int cur, int par, const T &pval) { // get cumulative sum vector buf; for (auto dst : g[cur]) { if (dst == par) continue; buf.push_back(f2(memo[dst], dst, cur)); } vector head(buf.size() + 1), tail(buf.size() + 1); head[0] = tail[buf.size()] = I; for (int i = 0; i < (int)buf.size(); i++) head[i + 1] = f1(head[i], buf[i]); for (int i = (int)buf.size() - 1; i >= 0; i--) tail[i] = f1(tail[i + 1], buf[i]); // update dp[cur] = par == -1 ? head.back() : f1(pval, head.back()); // propagate int idx = 0; for (auto &dst : g[cur]) { if (dst == par) continue; efs(dst, cur, f2(f1(pval, f1(head[idx], tail[idx + 1])), cur, dst)); idx++; } } }; /** * @brief Rerooting(全方位木DP) * @docs docs/tree/rerooting.md */ int main() { ios::sync_with_stdio(false); cin.tie(0); ll n;cin>>n; Graph g(n); rep(i,n-1){ ll a,b; cin>>a>>b; a--;b--; g[a].push_back(b); g[b].push_back(a); } vec ans(n); function dfs=[&](ll x,ll p,ll d){ ll res=INF; for(ll nx:g[x]){ if(nx==p)continue; chmin(res,dfs(nx,x,d+1)); } if(res==INF)res=0; ans[x]=min(d,res); res++; return res; }; dfs(0,-1,0); rep(i,n)cout<