题目意思：给一棵树，找到俩个不相交的通路，使得这俩个通路的长度和乘机最大；
解法：
小哥一看呵呵 这不就是枚举点 然后求俩边的树的直径在相乘求个最大值的题么！
呵呵 这个N 有100000 当时就不玩了；
学长指导了下我；
俺会了！/灯泡
在枚举点在书的直径上时点的左右的最长的链无非这几种情况如图（红色是树得直径）（蓝色和绿色是俩种情况）
无非就 蓝色和绿色这个俩种，所以这个答案和直径有很大的关系！
不在直径上时：一边肯定是直径了另一半呢？
如图；
解的过程：
1: 想求出直径的点顺序的 存在一个数组内；
2: 求出和每个直径上节点相邻的 最大和次大 和直径不相连的 链的 长度 并求出Max（这个链的点都不在直径上）
3：O（n）枚举点并求出这个点的左右的长度最值
4：由3的结果求出最大的ANS ，在和树得直径*Max取最值
over：
代码
#include <cstring> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; const int INF=0x7fffffff; const int maxn=100002; struct Edge { int to,pre; Edge (int to=0,int pre=0):to(to),pre(pre){} }; Edge edge[maxn*2]; int head[maxn],pos; bool vis[maxn]; bool in_line[maxn]; int ko[maxn],pos_ko; int dp[maxn][2]; int dp1[maxn],dp2[maxn]; struct info { int p,pre; }; info que[maxn]; void inint() { memset(head,-1,sizeof(head)); pos=pos_ko=0; memset(dp,0,sizeof(dp)); memset(in_line,false,sizeof(in_line)); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); } void add_edge(int s,int to) { edge[pos]=Edge(to,head[s]); head[s]=pos++; } void make(int P) { if(que[P].pre!=-1)make(que[P].pre); ko[pos_ko++]=que[P].p; in_line[que[P].p]=true; } int bfs(int t,bool flag) { memset(vis,false,sizeof(vis)); int h=0,r=1; que[0].p=t; que[0].pre=-1; vis[t]=true; int x; while(h<r) { x=que[h++].p; for(int i=head[x];~i;i=edge[i].pre) { Edge &tmp=edge[i]; if(!vis[tmp.to]) que[r].p=tmp.to, que[r++].pre=h-1, vis[tmp.to]=true; } } if(flag)make(r-1); return que[r-1].p; } void get_it(int key,int t) { if(key>dp[t][0])dp[t][1]=dp[t][0], dp[t][0]=key; else if(key>dp[t][1]) dp[t][1]=key; } int Max; int dfs(int pa,int &s,int &t) { int key,ans=0; for(int w=head[s];~w;w=edge[w].pre) { Edge &tmp=edge[w]; if(tmp.to==pa||in_line[tmp.to])continue; key=dfs(s,tmp.to,t); if(pa==-1) get_it(key,t); if(pa!=-1) { if(ans) Max=max(Max,ans-1+key); else Max=max(Max,key); } ans=max(ans,key+1); } if(pa==-1)Max=max(Max,ans-2); return ans==0?1:ans; } void solve(int &n) { long long ans=0; Max=0; int p1=bfs(1,false),p2=bfs(p1,true); int Max1; for(int i=0;i<pos_ko;i++) dfs(-1,ko[i],i); ans=(pos_ko-1)*Max; --pos_ko; for(int i=1;i<pos_ko;i++) { dp1[i]=max(dp1[i-1],i+dp[i][0]); dp1[i]=max(dp1[i],dp[i][0]+dp[i][1]); } for(int i=pos_ko-1;i>=0;i--) { dp2[i]=max(dp2[i+1],pos_ko-i+dp[i][0]); dp2[i]=max(dp2[i],dp[i][0]+dp[i][1]); } for(int i=1;i<pos_ko;i++) ans=max(ans,(long long)dp1[i]*dp2[i+1]); ans=max(ans,(long long )0); printf("%lld ",ans); } int main() { int n; int a,b; while(~scanf("%d",&n)) { inint(); for(int i=2;i<=n;i++) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } solve(n); } return 0; }