#include using namespace std; //頂点vの子供c1,c2...に対して //givep(v,merge(receive(c1),receive(c2),...))を計算する struct ReRooting{ using T = int; const T identity = 0; //mergeの演算に対する単位元 int n; vector> G; vector> dp; vector ans; //vのi番目の辺の子からRを受け取ったときの処理 T receive(int v,int i,T &R){ return T(R + 1); } //全体の累積lに子receiveの値をmerge //mergeの演算はモノイドでなくてはならない T merge(T l,T r){ return max(l, r); } //親に渡すときの処理 T givep(int v, T cum){ return cum; } ReRooting() {} ReRooting(int N):n(N){ G.resize(N); dp.resize(N); ans.resize(N,identity); } void add_edge(int a, int b) { G[a].emplace_back(b); G[b].emplace_back(a); } void read(){ int a, b; for(int i = 1; i < n; i++){ cin >> a >> b; a--, b--; G[a].emplace_back(b); G[b].emplace_back(a); } } void build() { dfs(0); // 普通に木DP dfs2(0, identity); // 残りの部分木に対応するDPを計算 } T dfs(int v, int p = -1) { T res = identity; int deg = G[v].size(); dp[v] = vector(deg, identity); for (int i = 0; i < deg; i++) { int u = G[v][i]; if (u == p) continue; dp[v][i] = dfs(u, v); res = merge(res, receive(v, i, dp[v][i]) ); } return givep(v, res); } void dfs2(int v, const T& dp_p, int p = -1) { int deg = G[v].size(); for (int i = 0; i < deg; i++) { // 前のdfsで計算した有向辺に対応する部分木のDPを保存 if (G[v][i] == p){dp[v][i] = dp_p; break;} } vector tmp(deg); vector dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積merge for (int i = 0; i < deg; i++) { dp_l[i + 1] = merge(dp_l[i], receive(v, i,dp[v][i])); tmp[i] = receive(v, i, dp[v][i]); } for (int i = deg - 1; i >= 0; i--) { dp_r[i] = merge(dp_r[i + 1], receive(v, i,dp[v][i])); } sort(tmp.begin(), tmp.end()); for(int i = 0; i < deg; i++){ ans[v] = max(ans[v], (deg - i) * tmp[i]); } for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算 int u = G[v][i]; if (u == p) continue; dfs2(u, givep(v, merge(dp_l[i], dp_r[i + 1])),v); } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; ReRooting g(n); g.read(); g.build(); int ans = 0; for(int v = 0; v < n; v++){ ans = max(ans, g.ans[v]); } cout << ans + 1 << '\n'; }