去掉一条边 剩下的2棵树的直径 乘积 求最大
列举每条边 2次bfs求直径 其实总共是 4*(n-1) 次bfs
总体时间 n-1*n;
#include#include #include #include #include #include using namespace std;#define LL long long#define MAXN 210#define inf 1000000000int 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 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\n",b.w,b.to); } } // printf("\n\n"); return b;}int main(){ int n; while(scanf("%d",&n)!=EOF) { cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i