//#include //using namespace std; //using ll=long long; //const ll ILL=2167167167167167167; //const int INF=2100000000; //#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) //#define all(p) p.begin(),p.end() //template using _pq = priority_queue, greater>; //template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} //template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} //template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} //template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} //bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} //template void vec_out(vector &p,int ty=0){ // if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} //template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} //template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} //int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} //template T square(T a){return a * a;} // // //std::vector> tree_in(int N){ // std::vector> G(N); // for(int i=0;i>a>>b; // a--,b--; // G[a].push_back(b); // G[b].push_back(a); // } // return G; //} //std::tuple,std::vector,std::vector> tree_order_pare_depth(std::vector> &G,int root=0){ // int n=G.size(); // std::vector order={root},pare(n,-1),depth(n); // pare[root]=-2; // for(int i=0;i tree_diameter_path(std::vector> &G){ // int n=G.size(); // auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1); // std::vector order,pare,depth,ans; // tie(order,pare,depth)=tree_order_pare_depth(G,r); // int ind=order[n-1]; // while(ind!=-2){ // ans.push_back(ind); // ind=pare[ind]; // } // return ans; //} // //#include "po167_library/graph/tree/LCA.hpp" // //void solve(); //// POP'N ROLL MUSIC / TOMOO //int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // // int t = 1; // // cin >> t; // rep(i, 0, t) solve(); //} // //void solve(){ // int N; // cin >> N; // vector> G(N); // vector A(N - 1), B(N - 1); // map, int> m; // rep(i, 0, N - 1){ // cin >> A[i] >> B[i]; // A[i]--, B[i]--; // G[A[i]].push_back(B[i]); // G[B[i]].push_back(A[i]); // m[{A[i], B[i]}] = i; // m[{B[i], A[i]}] = i; // } // auto D = tree_diameter_path(G); // po167::LCA L(G); // auto [order, pare, depth] = tree_order_pare_depth(G, D[0]); // ll base = 0; // int X = D.size(); // rep(i, 0, N) base += max(L.dist(i, D[0]), L.dist(i, D[X - 1])); // vector wei(N, 1); // rep(i, 0, N - 1){ // int a = order[N - i - 1]; // wei[pare[a]] += wei[a]; // } // vector ans(N - 1, base); // // cout << base << "\n"; // int P = 0, Q = 0; // rep(i, 0, N){ // if (L.dist(i, D[0]) == X - 1){ // chmax(Q, L.dist(i, D[X - 1]) / 2); // } // if (L.dist(i, D[X - 1]) == X - 1){ // chmax(P, L.dist(i, D[0]) / 2); // } // } // rep(i, 0, N - 1){ // int a = order[N - i - 1]; // int e = m[{a, pare[a]}]; // if (L.dist(a, D[0]) + L.dist(a, D[X - 1]) != X - 1){ // ans[e] -= wei[a]; // ans[e] -= max(L.dist(pare[a], D[0]), L.dist(pare[a], D[X - 1])); // } // else if (depth[a] <= P){ // ans[e] -= N - wei[a]; // ans[e] -= X - 1 - depth[a]; // } // else if (X - 1 - depth[a] < Q){ // ans[e] -= wei[a]; // ans[e] -= depth[a] - 1; // } // else if (depth[a] * 2 == X){ // ans[e] -= N - 1; // ans[e] -= X / 2; // } // else if (depth[a] * 2 < X){ // ans[e] -= wei[D[X / 2]]; // ans[e] -= N - wei[pare[a]]; // ans[e] -= X - depth[a]; // } // else{ // // ans[e] = -1; // // ans[e] -= wei[a]; // // ans[e] -= depth[a] - 1; // ans[e] -= N - wei[D[(X - 1) / 2]]; // ans[e] -= wei[a]; // ans[e] -= depth[pare[a]]; // } // } // for (auto x : ans) cout << x << "\n"; //} // #line 1 "d.cpp" #include using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using _pq = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} template T square(T a){return a * a;} std::vector> tree_in(int N){ std::vector> G(N); for(int i=0;i>a>>b; a--,b--; G[a].push_back(b); G[b].push_back(a); } return G; } std::tuple,std::vector,std::vector> tree_order_pare_depth(std::vector> &G,int root=0){ int n=G.size(); std::vector order={root},pare(n,-1),depth(n); pare[root]=-2; for(int i=0;i tree_diameter_path(std::vector> &G){ int n=G.size(); auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1); std::vector order,pare,depth,ans; tie(order,pare,depth)=tree_order_pare_depth(G,r); int ind=order[n-1]; while(ind!=-2){ ans.push_back(ind); ind=pare[ind]; } return ans; } #line 4 "/Users/Shared/po167_library/ds/Sparse_table.hpp" namespace po167{ template struct Sparse_table{ int n; int depth; std::vector> val; void init(std::vector &v){ depth = 1; n = v.size(); while ((1 << depth) <= n) depth++; val.resize(depth); val[0] = v; for (int i = 1; i < depth; i++){ val[i].resize(n); for (int j = 0; j <= n - (1 << i); j++){ val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]); } } } Sparse_table(std::vector v){ init(v); } Sparse_table(){} // 0 <= l < r <= n // if l == r : assert T prod(int l, int r){ assert(0 <= l && l < r && r <= n); int z=31-__builtin_clz(r-l); return op(val[z][l], val[z][r - (1 << z)]); } }; } #line 6 "/Users/Shared/po167_library/graph/tree/LCA.hpp" namespace po167{ int op(int a, int b){ return std::min(a, b); } struct LCA{ Sparse_table table; std::vector depth; std::vector E; std::vector order; int var_num; void init(std::vector> &g, int root = 0){ var_num = g.size(); assert(0 <= root && root < var_num); std::vector val; depth.assign(var_num, -1); depth[root] = 0; E.resize(var_num); std::vector tmp; order.clear(); tmp.reserve(var_num); order.reserve(var_num); int c = 0; auto dfs = [&](auto self, int var, int pare) -> void { E[var] = c++; if (var != root) tmp.push_back(E[pare]); order.push_back(var); for (auto x : g[var]) if (depth[x] == -1){ depth[x] = depth[var] + 1; self(self, x, var); } }; dfs(dfs, root, -1); assert(c == var_num); table.init(tmp); } void init(std::vector &pare){ int root = -1; int n = pare.size(); std::vector> g(n); for (int i = 0; i < n; i++){ if (pare[i] < 0){ assert(root == -1); root = i; } else{ assert(0 <= pare[i] && pare[i] < n); g[pare[i]].push_back(i); } } assert(root != -1); init(g, root); } LCA (std::vector> g, int root = 0){ init(g, root); } LCA (std::vector pare){ init(pare); } LCA(){ } int lca(int a, int b){ assert(0 <= std::min(a, b) && std::max(a, b) < var_num); if (a == b) return a; if (E[a] > E[b]) std::swap(a, b); return order[table.prod(E[a], E[b])]; } int dist(int a, int b){ assert(0 <= std::min(a, b) && std::max(a, b) < var_num); return depth[a] + depth[b] - 2 * depth[lca(a, b)]; } int back(int var, int len){ assert(len <= depth[var]); if (len == 0) return var; int l = 0, r = E[var]; while (r - l > 1){ int m = (l + r) / 2; if (depth[var] - depth[order[table.prod(m, E[var])]] < len){ r = m; } else l = m; } return order[table.prod(l, E[var])]; } // a -> b int jump(int a, int b, int len){ int c = lca(a, b); if (len <= depth[a] - depth[c]) return back(a, len); len -= depth[a] - depth[c]; if (len <= depth[b] - depth[c]) return back(b, depth[b] - depth[c] - len); return -1; } }; } #line 67 "d.cpp" void solve(); // POP'N ROLL MUSIC / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ int N; cin >> N; vector> G(N); vector A(N - 1), B(N - 1); map, int> m; rep(i, 0, N - 1){ cin >> A[i] >> B[i]; A[i]--, B[i]--; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); m[{A[i], B[i]}] = i; m[{B[i], A[i]}] = i; } auto D = tree_diameter_path(G); po167::LCA L(G); auto [order, pare, depth] = tree_order_pare_depth(G, D[0]); ll base = 0; int X = D.size(); rep(i, 0, N) base += max(L.dist(i, D[0]), L.dist(i, D[X - 1])); vector wei(N, 1); rep(i, 0, N - 1){ int a = order[N - i - 1]; wei[pare[a]] += wei[a]; } vector ans(N - 1, base); // cout << base << "\n"; int P = 0, Q = 0; rep(i, 0, N){ if (L.dist(i, D[0]) == X - 1){ chmax(Q, L.dist(i, D[X - 1]) / 2); } if (L.dist(i, D[X - 1]) == X - 1){ chmax(P, L.dist(i, D[0]) / 2); } } rep(i, 0, N - 1){ int a = order[N - i - 1]; int e = m[{a, pare[a]}]; if (L.dist(a, D[0]) + L.dist(a, D[X - 1]) != X - 1){ ans[e] -= wei[a]; ans[e] -= max(L.dist(pare[a], D[0]), L.dist(pare[a], D[X - 1])); } else if (depth[a] <= P){ ans[e] -= N - wei[a]; ans[e] -= X - 1 - depth[a]; } else if (X - 1 - depth[a] < Q){ ans[e] -= wei[a]; ans[e] -= depth[a] - 1; } else if (depth[a] * 2 == X){ ans[e] -= N - 1; ans[e] -= X / 2; } else if (depth[a] * 2 < X){ ans[e] -= wei[D[X / 2]]; ans[e] -= N - wei[pare[a]]; ans[e] -= X - depth[a]; } else{ // ans[e] = -1; // ans[e] -= wei[a]; // ans[e] -= depth[a] - 1; ans[e] -= N - wei[D[(X - 1) / 2]]; ans[e] -= wei[a]; ans[e] -= depth[pare[a]]; } } for (auto x : ans) cout << x << "\n"; } // 頼むーーーーーーー