#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; // constexpr int mod = 1000000007; constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } template struct ReRooting { using SubtreeMerge = function; using PrefixSuffixMerge = function; vector> g; const SubtreeMerge f1; const PrefixSuffixMerge f2; const T IE; vector subtree_dp, rerooting_dp; ReRooting(int V, const SubtreeMerge s, const PrefixSuffixMerge p, const T I) : g(V), f1(s), f2(p), IE(I), subtree_dp(V, I), rerooting_dp(V, I) {} void add_edge(int u, int v){ g[u].emplace_back(v); g[v].emplace_back(u); } void subtree_dfs(int from, int par){ for(int to : g[from]){ if(to != par){ subtree_dfs(to, from); subtree_dp[from] = f1(subtree_dp[from], subtree_dp[to]); } } if(subtree_dp[from] == IE) subtree_dp[from] = 0; } void rerooting_function(int cur, T par_val, int par){ int V = g[cur].size(); vector prefix(V + 1, IE), suffix(V + 1, IE); for(int i = 0; i < V; ++i){ int child = g[cur][i]; if(child == par) prefix[i + 1] = f1(prefix[i], par_val); else prefix[i + 1] = f1(prefix[i], subtree_dp[child]); } for(int i = V - 1; i >= 0; --i){ int child = g[cur][i]; if(child == par) suffix[i] = f1(suffix[i + 1], par_val); else suffix[i] = f1(suffix[i + 1], subtree_dp[child]); } for(int i = 0; i < V; ++i){ int child = g[cur][i]; if(child != par){ rerooting_dp[child] = f1(subtree_dp[child], f2(prefix[i], suffix[i + 1])); rerooting_function(child, f2(prefix[i], suffix[i + 1]), cur); } } } vector build(int root = 0){ subtree_dfs(root, -1); rerooting_function(root, IE, -1); rerooting_dp[root] = subtree_dp[root]; return rerooting_dp; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector> g(n); auto f = [](int a, int b){return min(a, b + 1);}; auto m = [](int a, int b){return min(a, b);}; ReRooting gg(n, f, m, INF); for(int i = 1; i < n; ++i){ int x, y; cin >> x >> y; --x, --y; g[x].emplace_back(y); g[y].emplace_back(x); gg.add_edge(x, y); } vector dep(n); auto dfs = [&](auto&& self, int from = 0, int d = 0, int par = -1) -> void { dep[from] = d; for(int to : g[from]){ if(to != par) self(self, to, d + 1, from); } }; dfs(dfs); auto dp = gg.build(); for(int i = 0; i < n; ++i){ cout << min(dep[i], dp[i]) << '\n'; } return 0; }