#include using namespace std; using ll = long long; void search(vector> &tree, vector> &dist, int u, int parent, vector &par) { par[u] = parent; int one = 0, two = 0; if (tree[u].size() == 1 and tree[u][0] == parent) { dist[u] = {0, 0}; return; } for (auto p : tree[u]) { if (p == parent) continue; search(tree, dist, p, u, par); if (two < dist[p].first + 1) { two = dist[p].first + 1; if (two > one) swap(one, two); } } dist[u] = {one, two}; } void solve() { // 各頂点から一番遠い点を保持していればよい。被った時のために二番目まで保持する int n; cin >> n; vector> tree(n + 1); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } // 一旦1を頂点とする vector par(n + 1, -1); vector> dist(n + 1, {-1, -1}); search(tree, dist, 1, -1, par); int ans = 0; queue que; que.push(1); while (!que.empty()) { int top = que.front(); que.pop(); vector roads; // それぞれの子どもについて考えてからpush for (auto p : tree[top]) { if (p == par[top]) continue; que.push(p); roads.push_back(dist[p].first); } if (par[top] != -1) { // 親が存在するとき、 if (dist[par[top]].first == dist[top].first + 1) { // 親からの最長経路が自分を通るとき roads.push_back(dist[par[top]].second); if (dist[top].second < dist[par[top]].second + 1) dist[top].second = dist[par[top]].second + 1; } else { // 親からの最長経路が自分を通らないとき roads.push_back(dist[par[top]].first); if (dist[top].second < dist[par[top]].first + 1) dist[top].second = dist[par[top]].first + 1; } if (dist[top].second > dist[top].first) swap(dist[top].first, dist[top].second); } // ansを更新 sort(roads.begin(), roads.end()); reverse(roads.begin(), roads.end()); for (int i = 0; i < (int)roads.size(); i++) { ans = max(ans, 1 + (i + 1) * (roads[i] + 1)); } } cout << ans << endl; } int main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(20); int CNT = 1; for (int i = 0; i < CNT; i++) solve(); }