Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define filer() freopen("in.txt","r",stdin)
- #define filew() freopen("out.txt","w",stdout)
- #define SET(a, x) memset((a), (x), sizeof(a))
- #define i64 long long
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<algorithm>
- #include<queue>
- #include<stack>
- #include<vector>
- #include <map>
- #define INF 1<<29
- using namespace std;
- int n;
- int adj[210][210];
- int dist[210];
- int deg[205];
- struct edge
- {
- int x,y;
- }I;
- int TRUE;
- vector<edge>E;
- int vst[205];
- struct node
- {
- int val;
- }z;
- vector<int>PQ;
- bool cmp(int a,int b)
- {
- return a>b;
- }
- queue<int>Q;
- int BFS(int S)
- {
- vst[S]=TRUE;
- dist[S]=0;
- int i,D=0;
- int u,v;
- Q.push(S);
- while(!Q.empty())
- {
- u=Q.front();
- Q.pop();
- for(i=1;i<=n;i++)
- {
- v=i;
- if(adj[u][v] && vst[v]!=TRUE)
- {
- vst[v]=TRUE;
- dist[v]=dist[u]+1;
- D=max(D,dist[v]);
- Q.push(v);
- }
- }
- }
- return D;
- }
- int main()
- {
- //filer();
- int T,cas=0,i,j,k,u,v,x,y;
- scanf("%d",&n);
- for(i=0;i<(n-1);i++)
- {
- scanf("%d%d",&u,&v);
- deg[u]++;
- deg[v]++;
- adj[u][v]++;
- adj[v][u]++;
- I.x=u;
- I.y=v;
- E.push_back(I);
- }
- int E_sz=n-1;
- int ans=0;
- for(i=0;i<E_sz;i++)
- {
- x=0;y=0;
- I=E[i];
- u=I.x;v=I.y;
- adj[u][v]--;
- adj[v][u]--;
- deg[u]--;deg[v]--;
- while(!PQ.empty())PQ.pop_back();
- TRUE++;
- for(j=1;j<=n;j++)
- {
- if(adj[u][j])
- {
- adj[u][j]--;
- adj[j][u]--;
- int ind=BFS(j);
- PQ.push_back(ind);
- adj[u][j]++;
- adj[j][u]++;
- }
- }
- sort(PQ.begin(),PQ.end(),cmp);
- for(j=0;j<=1 && j<PQ.size();j++)x+=(1+PQ[j]);
- while(!PQ.empty())PQ.pop_back();
- TRUE++;
- for(j=1;j<=n;j++)
- {
- if(adj[v][j])
- {
- adj[v][j]--;
- adj[j][v]--;
- int ind=BFS(j);
- PQ.push_back(ind);
- adj[v][j]++;
- adj[j][v]++;
- }
- }
- sort(PQ.begin(),PQ.end(),cmp);
- for(j=0;j<=1 && j<PQ.size();j++)y+=(1+PQ[j]);
- adj[u][v]++;
- adj[v][u]++;
- deg[u]++;deg[v]++;
- if((x*y)>ans)ans=x*y;
- }
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement