去掉一条边 剩下的2棵树的直径 乘积 求最大
列举每条边 2次bfs求直径 其实总共是 4*(n-1) 次bfs
总体时间 n-1*n;
#include<stdio.h> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> using namespace std; #define LL long long #define MAXN 210 #define inf 1000000000 int cnt; int head[MAXN]; struct edge { int fr,to,next; }edg[MAXN*4]; int x1,x2; void add(int u,int v) { edg[cnt].fr=u; edg[cnt].to=v; edg[cnt].next=head[u]; head[u]=cnt++; } struct node { int fa,to,w; }; queue<node>q1; node bfs1(int q) { node a; a.to=q; a.w=0; a.fa=0; q1.push(a); node b; b.w=0; b.to=0; while(!q1.empty()) { node now; now =q1.front(); q1.pop(); if(b.w< now.w) { b.w = now.w; b.to = now.to; } for(int i=head[now.to];i!=-1;i=edg[i].next) { node b; b.to=edg[i].to; if(now.fa==b.to) continue; if(now.to==x1&&b.to==x2||now.to==x2&&b.to==x1) continue; b.w=now.w+1; b.fa=now.to; q1.push(b); // printf("%d %d ",b.w,b.to); } } // printf(" "); return b; } int main() { int n; while(scanf("%d",&n)!=EOF) { cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } int ans=0; for(int i=0;i<cnt;i=i+2) { x1=edg[i].fr; x2=edg[i].to; node a1=bfs1(x1); node a2=bfs1(a1.to); node a3=bfs1(x2); node a4=bfs1(a3.to); // printf("%d %d ",a2.w,a4.w); ans =max(ans,a2.w*a4.w); } printf("%d ",ans); } return 0; }