#include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vmi = vector; using vvmi = vector; using vvvmi = vector; #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) struct RootedTreeLCA { int n; int LOG; vector> g; vector depth; vector par; vector> ch; vector> up; vector tin, tout; int timer; RootedTreeLCA(int n = 0) { init(n); } void init(int n_) { n = n_; g.assign(n, {}); depth.assign(n, 0); par.assign(n, -1); ch.assign(n, {}); tin.assign(n, 0); tout.assign(n, 0); timer = 0; LOG = 1; while ((1 << LOG) <= max(1, n)) LOG++; up.assign(LOG, vector(n, -1)); } void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int root = 0) { fill(par.begin(), par.end(), -1); fill(depth.begin(), depth.end(), 0); for (auto &v : ch) v.clear(); for (auto &row : up) fill(row.begin(), row.end(), -1); timer = 0; vector st; vector it(n, 0); st.reserve(n); st.push_back(root); par[root] = -1; depth[root] = 0; while (!st.empty()) { int v = st.back(); // first visit if (it[v] == 0) { tin[v] = timer++; } if (it[v] == (int)g[v].size()) { tout[v] = timer; st.pop_back(); continue; } int to = g[v][it[v]++]; if (to == par[v]) continue; par[to] = v; depth[to] = depth[v] + 1; ch[v].push_back(to); st.push_back(to); } for (int v = 0; v < n; v++) up[0][v] = par[v]; for (int j = 1; j < LOG; j++) { for (int v = 0; v < n; v++) { int p = up[j - 1][v]; up[j][v] = (p == -1 ? -1 : up[j - 1][p]); } } } // ===== 基本 API ===== int parent(int v) const { return par[v]; } const vector& children(int v) const { return ch[v]; } int get_depth(int v) const { return depth[v]; } vector adj(int v) const { vector res; if (par[v] != -1) res.push_back(par[v]); // parent for (int c : ch[v]) res.push_back(c); // children return res; } // ===== LCA ===== int kth_ancestor(int v, long long k) const { for (int j = 0; j < LOG; j++) { if (v == -1) return -1; if (k & (1LL << j)) v = up[j][v]; } return v; } int lca(int a, int b) const { if (depth[a] < depth[b]) swap(a, b); a = kth_ancestor(a, depth[a] - depth[b]); if (a == b) return a; for (int j = LOG - 1; j >= 0; j--) { if (up[j][a] != up[j][b]) { a = up[j][a]; b = up[j][b]; } } return up[0][a]; } int dist(int a, int b) const { int c = lca(a, b); return depth[a] + depth[b] - 2 * depth[c]; } // start:v, goal:u int jump_on_path(int v, int u, int t) const { int c = lca(v, u); int dv = depth[v] - depth[c]; int du = depth[u] - depth[c]; int d = dv + du; if (t < 0 || t > d) return -1; if (t <= dv) return kth_ancestor(v, t); return kth_ancestor(u, d - t); } int center_node_if_even_dist(int u, int v) const { int d = dist(u, v); if (d & 1) return -1; return jump_on_path(u, v, d / 2); } // is u in subtree of v? bool is_in_subtree(int u, int v) const { return tin[v] <= tin[u] && tin[u] < tout[v]; } }; using p = pair; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; RootedTreeLCA tr(n); rep(i, n-1){ int u, v; cin >> u >> v; tr.add_edge(u-1, v-1); }tr.build(0); vi tmp(n, 0); queue q; vector> down(n); rep(i, n){ tmp[i] = tr.children(i).size(); if(tmp[i] == 0){ //down[i].push_back({1, i}); q.push(i); } } while(!q.empty()){ auto u = q.front(); q.pop(); int v = tr.parent(u); sort(rall(down[u])); if(down[u].size() == 0){ down[v].push_back({1, u}); }else{ down[v].push_back({down[u][0].first+1, u}); } tmp[v]--; if(v == 0)continue; if(tmp[v] == 0)q.push(v); }sort(rall(down[0])); vi up(n, 0); for(auto i : tr.children(0))q.push(i); while(!q.empty()){ auto u = q.front(); q.pop(); int v = tr.parent(u); int tmp = up[v]; if(down[v].size() == 1){ up[u] = tmp; }else{ if(down[v][0].second != u){ tmp = max(tmp, down[v][0].first); }else{ tmp = max(tmp, down[v][1].first); } up[u] = tmp; } up[u]++; for(auto j : tr.children(u))q.push(j); } int ans = 0; rep(i, n){ vi v; v.push_back(up[i]); for(auto j : down[i])v.push_back(j.first); sort(all(v)); int l = v.size(); rep(j, l){ int c = v[j]*(l-j); ans = max(ans, c+1); } }cout << ans << endl; return 0; }