题目背景
马奥雷利亚诺布恩迪亚上校发动了他的第三十二次战争，让我们祝他好运。
题目描述
马孔多附近有n个城市， 有n-1条双向道路连通这些城市。上校想通过摧毁两条公路的方式对当局予以威慑。但是上校的老师 告诉他为了战略目的这两条路不可以有共同的城市。这次行动对当局的威慑效果将等于两条路径的长 度的乘积。假设每条道路的长度等于1，并且路径的长度等于道路的数量。请你帮上校造成最大的威 慑。
输入格式
单组测试数据。第一行是一个整数 n (2≤n≤200) ，n是这个马孔多附近城市的数量。接下来n-1行是 道路的信息，每一行是两个整数ai,bi，它们是城市的编号，表示ai和bi之间有一条道路直接连通。 (1≤ai,bi≤n)。
输出格式
输出最大的威慑
输入输出样例
输入输出样例
输入 #1复制
4
1 2
2 3
3 4
输出 #1复制
1
输入 #2复制
2
2 1
输出 #2复制
0
输入 #3复制
6
1 2
2 3
2 4
5 4
6 4
输出 #3复制
4
说明/提示
对于35%的数据， n <= 10 对于75%的数据， n <= 100 对于100%的数据， n <= 200
思路十分简单，直接枚举每条边，将其删掉，形成两棵树，以两边的定点为起点分别找树的直径。
？？？
So，why is this right?
如此考虑：
题目中要求我们路径上不能有交叉，同时长度要尽量大。
对于条件2，很容易想到求树的直径。对于条件1，可以如此模拟：
要使得路径尽量长，就要走过尽可能多的边。那么，最好的方法是什么？
让两条道路相差的尽可能不远。既然如此，那么最不远的两个点是什么点？
一条边的两个端点。于是，断开这条边防止交叉，然后求分别跑树的直径即可。
AC利器：
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define ll long long/*断开一条边后分成两棵树，求两棵树的直径 */ inline int read(){
int x = , s = ;
char c = getchar();
while(!isdigit(c)){
if(c == '-') s = -;
c = getchar();
}
while(isdigit(c)){
x = (x << ) + (x << ) + (c ^ '');
c = getchar();
}
return x * s;
}struct node{
int u, v;
int next;
}t[N];
int f[N];
bool vis[N];
int dp[N];
int ans = , temp = , temp1 = ;int bian = ;
inline void add(int u, int v){
t[++bian].u = u;
t[bian].v = v;
t[bian].next = f[u];
f[u] = bian;
return ;
}void dfs(int now){
for(int i = f[now]; i;i = t[i].next){
int v = t[i].v, u = t[i].u;
if(!vis[v]){
vis[v] = ;
dfs(v);
temp = max(temp, dp[u] + dp[v] + );
dp[u] = max(dp[u], dp[v] + );
}
}
return ;
}int main(){
// freopen("terrorize.in","r",stdin);
// freopen("terrorize.out","w",stdout);
int n = read();
for(int i = ;i <= n - ;i ++){
int x = read(), y = read();
add(x, y);
add(y, x);
}
for(int i= ;i <= bian;i += ){
memset(vis, , sizeof(vis));
memset(dp, , sizeof(dp));
int v = t[i].v, v2 = t[i+].v;
vis[v] = vis[v2] = ;
temp1 = temp = ;
dfs(v);
temp1 = temp;
temp = ;
dfs(v2);
ans = max(ans, temp * temp1);
}
cout << ans << endl;
return ;
}
