- 1
- /*
- 2 ID: y1197771
- 3 PROG: test
- 4 LANG: C++
- 5 */
- 6#include 7#define pb push_back 8#define FOR(i, n) for (int i = 0; i < (int) n; ++i) 9#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 10 typedef long long ll;
- 11 using namespace std;
- 12 typedef pair < int,
- int > pii;
- 13 const int maxn = 2e2 + 10;
- 14 int e[maxn][maxn];
- 15 int n;
- 16 vector a;
- 17 int ans;
- 18 int work(int u, int p) {
- 19 int x,
- y;
- 20 x = y = 0;
- 21
- for (int i = 1; i <= n; i++) {
- 22
- if (e[u][i] && i != p) {
- 23 int t = work(i, u);
- 24
- if (t > y) y = t;
- 25
- if (y > x) swap(x, y);
- 26
- }
- 27
- }
- 28 ans = max(ans, x + y + 1);
- 29
- return x + 1;
- 30
- }
- 31 void solve() {
- 32
- while (cin >> n) {
- 33 memset(e, 0, sizeof e);
- 34 int x,
- y;
- 35 a.clear();
- 36
- for (int i = 0; i < n - 1; i++) {
- 37 cin >> x >> y; //cout << x << " " << y << endl;
- 38 e[x][y] = 1;
- 39 e[y][x] = 1;
- 40 a.pb({
- x,
- y
- });
- 41 42
- }
- 43 44 int res = 0;
- 45 46
- for (int i = 0; i < n - 1; i++) {
- 47 x = a[i].first,
- y = a[i].second;
- 48 e[x][y] = e[y][x] = 0;
- 49 int t1,
- t2;
- 50 t1 = t2 = 0;
- 51 ans = 0;
- 52 work(x, 0);
- 53 t1 = max(0, ans - 1);
- 54 ans = 0;
- 55 work(y, 0);
- 56 t2 = max(0, ans - 1);
- 57 res = max(res, t1 * t2);
- 58 e[x][y] = e[y][x] = 1;
- 59
- }
- 60 cout << res << endl;
- 61
- }
- 62
- }
- 63 int main() {
- 64 freopen("test.in", "r", stdin);
- 65 //freopen("test.out", "w", stdout);
- 66 ios: :sync_with_stdio(0);
- 67 cin.tie(0);
- cout.tie(0);
- 68 solve();
- 69
- return 0;
- 70
- }
来源: http://www.bubuko.com/infodetail-2000995.html