Problem - 14D - Codeforces
题意:
求一棵树上两条不相交直径的最大乘积。
题解：
由于n<200，考虑枚举每个点断开的情况，从断开的两端求直径。
代码：
/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const double E = exp(1);
const double PI = acos(-1.0);
const int maxn=4e5+10;
const int Mod=1e9+7;
int n,tot,d,head[maxn],rt,d1[maxn],d2[maxn];
struct QwQ{int nxt,v,id;
}e[maxn];
void add(int x,int y,int id){e[++tot].v=y;e[tot].id=id;e[tot].nxt=head[x];head[x]=tot;
}
void dfs(int x,int fa,int id){for(int i=head[x];i;i=e[i].nxt){int v=e[i].v;if(v==fa) continue;if(e[i].id==id) {rt=e[i].v;continue;}dfs(v,x,id);if(d1[x]<d1[v]+1) {d2[x]=d1[x];d1[x]=d1[v]+1;}else if(d1[v]+1>d2[x]) d2[x]=d1[v]+1;d=max(d,d1[x]+d2[x]);}
}
string s;
signed main(){n=read();for(int i=1;i<n;i++){int u=read(),v=read();add(u,v,i);add(v,u,i); }int ans=-1;for(int i=1;i<n;i++){d=0;rt=0;dfs(1,0,i);memset(d1,0,sizeof(d1));memset(d2,0,sizeof(d2));int l1=d;d=0;dfs(rt,0,i);memset(d1,0,sizeof(d1));memset(d2,0,sizeof(d2));ans=max(ans,l1*d);// cout<<l1<<" "<<d<<endl;}cout<<ans<<endl;
}