#include using namespace std; #pragma region templates struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init; using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; using i128= __int128_t; template using minpq=priority_queue,greater>; #define rep(i, x, limit) for(int i=(x); i< (limit); ++i) #define REP(i, x, limit) for(int i=(x); i<=(limit); ++i) #define all(x) std::begin(x), std::end(x) #define rall(x) std::rbegin(x), std::rend(x) #define el '\n' #define spa ' ' #define Yes cout<<"Yes"< void write_value(const T &target){ using V = std::decay_t; if constexpr(ostreamable_v){ std::cout<){ std::cout<<'{'; write_value(target.first); std::cout<<','; write_value(target.second); std::cout<<'}'; }else if constexpr(iterable_v){ std::cout<<'['; bool first=true; for(const auto &e:target){ if(!first) std::cout<<", "; write_value(e); first=false; } std::cout<<']'; }else if constexpr(std::is_convertible::value){ write_value(i128_to_str(target)); }else if constexpr(std::is_convertible_v){ write_value(static_cast(target)); }else if constexpr(stack_like_v){ auto tmp=target; std::cout<<'['; bool first=true; while(!tmp.empty()){ if(!first) std::cout<<", "; write_value(tmp.top()); tmp.pop(); first=false; } std::cout<<']'; }else if constexpr(queue_like_v){ auto tmp=target; std::cout<<'['; bool first=true; while(!tmp.empty()){ if(!first) std::cout<<", "; write_value(tmp.front()); tmp.pop(); first=false; } std::cout<<']'; } else{ std::cerr<<"Invalid Output: Unwritable variable detected"< void output(const T &target, const Rest&... rest){ write_value(target); if constexpr(sizeof...(rest)>0){ std::cout<<' '; output(rest...); }else{ std::cout<<'\n'; } } template bool chmin(T1 &a,T2 b){return a>b?a=b,true:false;} template bool chmax(T1 &a,T2 b){return a=0); if(a==0 and b==0) return 1; if(a==1) return 1; if(a==-1) return (b&1)?-1:1; ll res=1; while(b){ if(b&1) res*=a; b>>=1; if(b) a*=a; } return res; } // 二分探索による、浮動小数点型を介さないsqrt // 制約:0 <= x <= LLONG_MAX ll ll_sqrt(ll x){ assert(0 <= x); ll ok = 0, ng = x/2+2; while(abs(ok-ng) > 1){ ll mid = (ok+ng)/2; if(x/mid < mid) ng = mid; else ok = mid; } return ok; } // 浮動小数点型を介さず、aを底とした対数関数 log_a(x)以上の最小の整数を返す // 制約: 0 < x <= LLONG_MAX, 1 < a <= LLONG_MAX ll ll_log(ll x, ll a = 2){ assert(x > 0 && a > 1); ll res = 0; while(x > 1){ x = (x+a-1)/a; res++; } return res; } // Pythonのenumerateみたいなやつ [index,value]を範囲for文に提供 template vector> enumerate(const vector &v){ vector> res(ssize(v)); for(int i=0;i> enumerate(const string &s){ vector> res(ssize(s)); for(int i=0;i vector multipleSort(Compare comp = Compare(), Vectors&... vectors) { const size_t size = std::get<0>(std::tie(vectors...)).size(); ((void)std::initializer_list{(vectors.size() == size ? 0 : throw std::invalid_argument("Vectors must have the same size"))...}); std::vector indices(size); std::iota(indices.begin(), indices.end(), 0); std::sort(indices.begin(), indices.end(), [&](size_t i, size_t j) { return comp(std::get<0>(std::tie(vectors...))[i], std::get<0>(std::tie(vectors...))[j]); }); auto reorder = [&](auto& vec) { auto temp=vec; for (size_t i = 0; i < size; ++i) { vec[i] = temp[indices[i]]; } }; (reorder(vectors), ...); return indices; } #pragma endregion templates /*//-------------------------------------------------------- refer to: https://trap.jp/post/1702/ noya2さんに感謝 全方位木DP モノイドを載せて全頂点それぞれ根としてN回木DPする感じ. Eがメインの型、Vは辺のポテンシャルの型という感じだが基本E==Vでよい merge: Eの二項演算(モノイド)を載せて、部分木同士を合併 e(): 単位元 put_edge: 辺を移動するときに値(E)に何か作用させる感じ. ポテンシャル等. +1とかはここに書くがち(merge(a,e())=aを意識して.) put_vertex: dp[頂点]に値を書く. つまりmergeで得た値E valがあって dp[頂点]=put_vertex(val)って感じ. +1とかも同上. put_edge, put_vertexのiはよくわかんない… 基本無視でok build(root=0)の返り値でroot中心の木DP結果が見れる *///-------------------------------------------------------- template struct RerootingDP { struct edge { int to, idx, xdi; }; RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) { es.resize(2*n-2); start.resize(2*n-2); if (n == 1) es_build(); } void add_edge(int u, int v, int idx, int xdi){ start[inner_edge_id] = u; es[inner_edge_id] = {v,idx,xdi}; inner_edge_id++; start[inner_edge_id] = v; es[inner_edge_id] = {u,xdi,idx}; inner_edge_id++; if (inner_edge_id == 2*n-2){ es_build(); } } vector build(int root_ = 0){ root = root_; vector subdp(n); subdp[0] = put_vertex(e(),0); outs.resize(n); vector geta(n+1,0); for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1; geta[root+1]++; for (int i = 0; i < n; i++) geta[i+1] += geta[i]; auto dfs = [&](auto sfs, int v, int f) -> void { E val = e(); for (int i = start[v]; i < start[v+1]; i++){ if (es[i].to == f){ swap(es[start[v+1]-1],es[i]); } if (es[i].to == f) continue; sfs(sfs,es[i].to,v); E nval = put_edge(subdp[es[i].to],es[i].idx); outs[geta[v]++] = nval; val = merge(val,nval); } subdp[v] = put_vertex(val, v); }; dfs(dfs,root,-1); return subdp; } vector reroot(){ vector reverse_edge(n); reverse_edge[root] = e(); vector answers(n); auto dfs = [&](auto sfs, int v) -> void { int le = outs_start(v); int ri = outs_start(v+1); int siz = ri - le; vector rui(siz+1); rui[siz] = e(); for (int i = siz-1; i >= 0; i--){ rui[i] = merge(outs[le+i],rui[i+1]); } answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v); E lui = e(); for (int i = 0; i < siz; i++){ V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v); reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi); lui = merge(lui,outs[le+i]); sfs(sfs,es[start[v]+i].to); } }; dfs(dfs,root); return answers; } private: int n, root, inner_edge_id; vector outs; vector es; vector start; int outs_start(int v){ int res = start[v] - v; if (root < v) res++; return res; } void es_build(){ vector nes(2*n-2); vector nstart(n+2,0); for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++; for (int i = 0; i < n; i++) nstart[i+1] += nstart[i]; for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i]; swap(es,nes); swap(start,nstart); } }; struct node{ ll ma,mi,cnt,val; }; node merge(node a,node b){ return {max(a.ma,b.ma),min(a.mi,b.mi),a.cnt+b.cnt,0}; } node e(){ return {-inf,inf,0,0}; } node put_edge(node V,int idx){ V.mi++; V.ma++; V.cnt++; return V; } node put_vertex(node E,int v){ if(E.mi==inf) E.mi=0; if(E.ma==-inf) E.ma=0; if(E.cnt==1) E.val=E.ma+1; else E.val=E.mi*E.cnt+1; E.cnt=0; return E; } int main(){ /*//-------------------------------------------------------- ある頂点rを根として、それを中心としたウニ頂点数maxですか LCAの条件がちょっとわからんな どうしたらいいんだ 部分木mergeで部分木の葉までの距離 min を取るとなんかよさそう(?) 距離min * children_cnt +1 が解じゃないか いやmerge演算では部分木の距離をmaxでとる感じかも putVではminね いやputVでmin取りようがないですやん じゃあ両方保持してまえ node:={葉までのdistのmax,min,直接のchildren_cnt,答えval} *///-------------------------------------------------------- int N; cin>>N; RerootingDP G(N); rep(i,0,N-1){ int u,v; cin>>u>>v; G.add_edge(u-1,v-1,i,i); } // for(auto [a,b,c,d]:G.build(0)) output(a,b,c,d); G.build(); ll ans=0; for(auto e:G.reroot()) chmax(ans,e.val); output(ans); }