#include using namespace std; struct HLD2{ //2.辺のみパターン. int n = 0,tim = 0; vector dist,in,out,siz,head,pre,par; vector connect; vector make(vector>> &Graph){ n = Graph.size(); dist.resize(n),in.resize(n),siz.resize(n,1),out.resize(n); head.resize(n),par.resize(n),connect.resize(n); auto dfs1 = [&](auto dfs1,int pos,int back = -1,int d = 0) -> void { par.at(pos) = back; dist.at(pos) = d; if(Graph.at(pos).size() && Graph.at(pos).at(0).first == back) swap(Graph.at(pos).at(0),Graph.at(pos).back()); for(auto &to : Graph.at(pos)){ if(to.first == back) continue; dfs1(dfs1,to.first,pos,d+1); siz.at(pos) += siz.at(to.first); if(siz.at(Graph.at(pos).at(0).first) < siz.at(to.first)) swap(Graph.at(pos).at(0),to); } }; vector ret(n); auto dfs2 = [&](auto dfs2,int pos,int back = -1) -> void { in.at(pos) = tim++; for(auto &[to,w] : Graph.at(pos)){ if(to == back) continue; if(to == Graph.at(pos).at(0).first) head.at(to) = head.at(pos),ret.at(tim-1) = w; else head.at(to) = to,connect.at(to) = w; //頂点との変更点1. dfs2(dfs2,to,pos); } out.at(pos) = tim; }; dfs1(dfs1,0); dfs2(dfs2,0); return ret; } vector> findpath(int u,int v){ //dfs行きがけ順に並べた頂点のセグ木の区間を返す. //R = -1はconnect[L]の値. //行きがけ順はrep(0-n)give[in[i]]=A[i]. //交換法則が成り立たたない場合は修正いる. vector> ret; while(head.at(u) != head.at(v)){ if(dist.at(head.at(u)) > dist.at(head.at(v))) swap(u,v); if(head.at(v) != v) ret.push_back({in.at(head.at(v)),in.at(v)}); ret.push_back({head.at(v),-1}); v = par.at(head.at(v)); } if(in.at(u) > in.at(v)) swap(u,v); if(u != v) ret.push_back({in.at(u),in.at(v)}); return ret; } }; using SS = long long; using FF = long long; class LazySegmentTree{ //ACL超参考にしてる というかパクリ. //verify十分だけど注意. private: vector dat; vector lazy; public: int siz = -1,n = -1,log = 0; SS op(SS a,SS b){return a+b;} SS mapping(FF f, SS x){return f+x;} FF composition(FF f, FF g){return f+g;} SS e(){return 0;} FF id(){return 0;} //op区間演算 mapping lazy→data composition lazy→lazy //e 単位元 id map(id,a)=a LazySegmentTree(int N){init(N);} LazySegmentTree(const vector &A){//配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.resize(siz,id()); for(int i=0; i0; i--) merge(i); } void init(int N){ //単位元になる. siz = 1; n = N; log = 0; while(siz < n) siz *= 2,log++; dat.assign(siz*2,e()); lazy.assign(siz,id()); } void init(const vector &A){ //配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.assign(siz,id()); for(int i=0; i0; i--) merge(i); } private: void eval(int u,FF f){ //u番目にfを適用したあと保留. if(u == 0) return; dat.at(u) = mapping(f,dat.at(u)); if(u < siz) lazy.at(u) = composition(f,lazy.at(u)); } void spread(int u){ //uにあるFF保留を伝播. if(u == 0 || id() == lazy.at(u)) return; eval(2*u,lazy.at(u)); eval(2*u+1,lazy.at(u)); lazy.at(u) = id(); } void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ. public: void set(int pos,SS x){ //1点変更. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = x; while(pos > 1) pos >>= 1,merge(pos); } void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = mapping(f,dat.at(pos)); while(pos > 1) pos >>= 1,merge(pos); } void update(int l,int r,FF f){ //区間更新. assert(0 <= l && l <= r && r <= n); if(l == r) return; l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<>i); if(((r>>i)<>i); } int memoL = l,memoR = r; while(l < r){ if(l&1) eval(l++,f); if(r&1) eval(--r,f); l >>= 1; r >>= 1; } l = memoL,r = memoR; while((l&1) == 0) l >>= 1; while((r&1) == 0) r >>= 1; r--; //-1注意. while(l > 1) l >>= 1,merge(l); while(r > 1) r >>= 1,merge(r); } SS get(int pos){ //1点取得. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); return dat.at(pos); } SS rangeans(int l,int r){ //区間取得. assert(0 <= l && l <= r && r <= n); if(l == r) return e(); l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<>i); if(((r>>i)<>i); } SS retl = e(),retr = e(); while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS allrange(){return dat.at(1);} //全体取得. int maxright(const function f,int l = 0){ assert(0 <= l && l <= n && f(e())); if(l == n) return n; l += siz; for(int i=log; i>0; i--) spread(l>>i); SS now = e(); do{ while(l%2 == 0) l >>= 1; SS next = op(now,dat.at(l)); if(f(next) == false){ while(l < siz){ spread(l); l <<= 1; next = op(now,dat.at(l)); if(f(next)) now = next,l++; } return l-siz; } now = next; l++; }while((l&-l) != l); return n; } int minleft(const function f,int r = -1){ if(r == -1) r = n; assert(0 <= r && r <= n && f(e())); if(r == 0) return 0; r += siz; for(int i=log; i>0; i--) spread((r-1)>>i); SS now = e(); do{ r--; while(r&1) r >>= 1; if(r == 0) r = 1; SS next = op(dat.at(r),now); if(f(next) == false){ while(r < siz){ spread(r); r <<= 1; r++; next = op(now,dat.at(r)); if(f(next)) now = next,r--; } return r+1-siz; } now = next; }while((r&-r) != r); return 0; } }; template class Cumulative{ //1次元. private: T op(T a,T b){ auto [a1,a2,da] = a; auto [b1,b2,db] = b; if(a1 == b1) return {a1,b1,-2}; if(a2 >= b1) return a; if(b2 >= a2) return b; if(a1 > b1) return {a1,b1,da}; return {b1,a1,db}; } T inv(T a){return a;} //ない場合はスルー->rangeans使用不可. T e(){return {0,0,-2};} int n; vector L,R; public: Cumulative(){} Cumulative(vector &A){make(A);} void make(vector &A){ L = A,R = A; n = A.size(); for(int i=1; i=0; i--) R.at(i) = op(R.at(i),R.at(i+1)); } T rangeans(int l,int r){ //[l,r]だよL<0も許容 逆元はいる. if(l > r || r < 0) return e(); T ret = L.at(r); if(l > 0) ret = op(ret,inv(L.at(l-1))); return ret; } T skipone(int pos){ //0<=pos 0) ret = L.at(pos-1); if(pos != n-1) ret = op(ret,R.at(pos+1)); return ret; } T skiprange(int l,int r){//l<=r. T ret = e(); if(l > 0) ret = L.at(l-1); if(r != n-1) ret = op(ret,R.at(r+1)); return ret; } T get(int pos){return L.at(pos);} vector allA(){return L;} }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector>> Graph(N); for(int i=0; i> u >> v; u--; v--; Graph.at(u).push_back({v,i}); Graph.at(v).push_back({u,i}); } HLD2 H; H.make(Graph); LazySegmentTree Z(N); vector minus(N); long long sum = 0; using T = tuple; vector par(N,-1); vector> kid(N); { auto dfs = [&](auto dfs,int pos,int back) -> T { int ret1 = 0,ret2 = 0,ret3 = pos; int n = Graph.at(pos).size(); kid.at(pos).resize(n); for(int i=0; i= ret1) ret1 = one,ret2 = two,ret3 = down; else if(ret2 >= one){} else{ if(ret1 > one) ret2 = one; else ret2 = ret1,ret1 = one,ret3 = down; } } ret1++,ret2++; return {ret1,ret2,ret3}; }; dfs(dfs,0,-1); } vector answer(N-1); { auto dfs = [&](auto dfs,int pos,int back,T take,int epos = -1) -> void { if(back != -1) kid.at(pos).at(par.at(pos)) = take; Cumulative C(kid.at(pos)); int n = Graph.at(pos).size(); auto [one,two,down] = C.get(n-1); sum += one; if(down == -2) down = pos; if(down != pos){ for(auto [l,r] : H.findpath(pos,down)){ if(r == -1) minus.at(l)++; else Z.update(l,r,1); } } if(epos != -1){ int t1 = H.in.at(pos),t2 = H.out.at(pos),t3 = H.in.at(down); if(t1 <= t3 && t3 < t2) answer.at(epos) -= one; else answer.at(epos) -= one-1; } for(int i=0; i to) continue; for(auto [l,r] : H.findpath(i,to)){ if(r == -1) answer.at(epos) -= minus.at(l); else answer.at(epos) -= Z.get(l); } } } for(auto a : answer) cout << a+sum << "\n"; }