#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i struct Edge{ int from,to; T weight; int index; Edge(int from_,int to_,T weight_=T(),int index_=-1):from(from_),to(to_),weight(weight_),index(index_){} Edge():from(-1),to(-1),weight(),index(-1){} friend std::ostream &operator<<(std::ostream &os,const Edge&e){ os<<'['; os<<"from:"< struct Tree{ protected: int n,r; std::vector>edge; std::vector>g; std::vectorptr; struct tree_range{ using iterator=typename std::vector>::iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} bool empty()const{return !size();} Edge &operator[](int i)const{return l[i];} }; struct const_tree_range{ using iterator=typename std::vector>::const_iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} bool empty()const{return !size();} const Edge &operator[](int i)const{return l[i];} }; public: explicit Tree(int n_):n(n_){ edge.reserve(n-1); } Tree():n(0){} Tree(int n_,const std::vector>&e,bool dir=false):n(n_),r(-1),edge(e){ if(!dir)build(); else{ std::vectorseen(n,false); ptr.resize(n+1); for(const Edge&i:edge)ptr[i.from]++,ptr[i.to]++,seen[e.to]=true; for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; r=std::find(seen.begin(),seen.end(),false)-seen.begin(); assert(ptr[n]==n*2-2); g.resize(ptr[n]); for(const Edge&i:edge)g[--ptr[i.to]]=Edge(i.to,i.from,i.weight,i.index); for(const Edge&i:edge)g[--ptr[i.from]]=i; } } template void read(){ for(int i=0;i>u>>v; if constexpr(index)u--,v--; if constexpr(weighted)std::cin>>w; else w=1; edge.emplace_back(u,v,w,i); } build(); } template void readp(){ ptr.resize(n+1); for(int i=1;i>p; if constexpr(index)p--; edge.emplace_back(p,i,1,i-1); ptr[p]++; ptr[i]++; } for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; g.resize(n*2-2); for(auto&&[u,v,w,i]:edge)g[--ptr[v]]=Edge(v,u,w,i); for(int i=0;ipar(n,-1); par[root]=-1; std::queueque; que.push(root); while(!que.empty()){ int x=que.front(); que.pop(); for(int i=ptr[x];i&e=g[i]; if(e.to!=par[x]){ par[e.to]=x; edge[e.index]=e; que.push(e.to); i++; } else{ if(i+1==ptr[x+1])break; std::swap(g[i],g[ptr[x+1]-1]); } } } r=root; } std::vectorbfs_order()const{ assert(is_directed()); std::vectorbfs(n); int p=0,q=0; bfs[q++]=root(); while(p&e:(*this)[x])bfs[q++]=e.to; } return bfs; } std::vectordfs_order()const{ assert(is_directed()); std::vectorres; res.reserve(n); std::vectorst(n); int p=0; st[p++]=root(); while(p){ int x=st[--p]; res.push_back(x); p+=(*this)[x].size(); for(const Edge&e:(*this)[x])st[--p]=e.to; p+=(*this)[x].size(); } return res; } std::vectorrbfs_order()const{ std::vectorbfs=bfs_order(); std::reverse(bfs.begin(),bfs.end()); return bfs; } void hld(){ assert(is_directed()); std::vectorsub(n); for(int x:rbfs_order()){ sub[x]=1; int mx=-1; for(Edge&e:(*this)[x]){ sub[x]+=sub[e.to]; if(mx,std::vector>in_out_order(){ assert(is_directed()); std::vectorin(n),out(n); int p=0; auto dfs=[&](auto self,int x)->void { in[x]=p++; for(const Edge&e:(*this)[x]){ self(self,e.to); } out[x]=p; }; dfs(dfs,root()); return std::make_pair(in,out); } std::pair>diameter()const{ assert(!is_directed()); static constexpr T inf=std::numeric_limits::max(); std::vectordst(n,inf); dst[0]=0; std::vectorque(n); int p=0,q=1; que[0]=0; while(p&e:(*this)[x])if(dst[e.to]==inf){ dst[e.to]=dst[x]+e.weight; que[q++]=e.to; } } int u=std::max_element(dst.begin(),dst.end())-dst.begin(); std::fill(dst.begin(),dst.end(),inf); dst[u]=0; p=0,q=1; que[0]=u; while(p&e:(*this)[x])if(dst[e.to]==inf){ dst[e.to]=dst[x]+e.weight; que[q++]=e.to; } } int v=std::max_element(dst.begin(),dst.end())-dst.begin(); T weight=dst[v]; std::vectorres; while(u!=v){ res.push_back(v); for(const Edge&e:(*this)[v])if(dst[e.to]& get_edge(int i)const{return edge[i];} inline int parent(int i)const{return i==r?-1:g[ptr[i+1]-1].to;} inline int root()const{return r;} typename std::vector>::iterator begin(){return edge.begin();} typename std::vector>::iterator end(){return edge.end();} typename std::vector>::const_iterator begin()const{return edge.begin();} typename std::vector>::const_iterator end()const{return edge.end();} }; void SOLVE(){ int n; cin>>n; Tree t(n); t.read(); vectordep(n); int ans=0; auto dfs=[&](auto self,int x,int p)->void { dep[x]=1; for(auto e:t[x])if(e.to!=p){ self(self,e.to,x); chmax(dep[x],dep[e.to]+1); } }; auto dfs2=[&](auto self,int x,int p)->void { vectoradj; for(auto e:t[x])adj.push_back(dep[e.to]); sort(all(adj)); rep(i,adj.size()){ chmax(ans,1+adj[i]*(adj.size()-i)); } vectorleft(t[x].size()),right(t[x].size()); rep(i,t[x].size())left[i]=right[i]=dep[t[x][i].to]; rep(i,1,left.size())chmax(left[i],left[i-1]); for(int i=ssize(right)-2;i>=0;i--)chmax(right[i],right[i+1]); rep(i,t[x].size())if(t[x][i].to!=p){ dep[x]=0; if(i)chmax(dep[x],left[i-1]); if(i+1!=t[x].size())chmax(dep[x],right[i+1]); dep[x]++; self(self,t[x][i].to,x); } }; dfs(dfs,0,-1); dfs2(dfs2,0,-1); cout<