Advertisement
farsid

Untitled

Aug 5th, 2012
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. #define filer() freopen("in.txt","r",stdin)
  2. #define filew() freopen("out.txt","w",stdout)
  3. #define SET(a, x) memset((a), (x), sizeof(a))
  4. #define i64 long long
  5. #include<iostream>
  6. #include<stdio.h>
  7. #include<string.h>
  8. #include<math.h>
  9. #include<algorithm>
  10. #include<queue>
  11. #include<stack>
  12. #include<vector>
  13. #include <map>
  14. #define INF 1<<29
  15.  
  16. using namespace std;
  17.  
  18. int n;
  19.  
  20. int adj[210][210];
  21.  
  22. int dist[210];
  23.  
  24. int deg[205];
  25.  
  26. struct edge
  27. {
  28. int x,y;
  29. }I;
  30.  
  31. int TRUE;
  32.  
  33. vector<edge>E;
  34.  
  35. int vst[205];
  36.  
  37. struct node
  38. {
  39. int val;
  40. }z;
  41.  
  42. vector<int>PQ;
  43.  
  44. bool cmp(int a,int b)
  45. {
  46. return a>b;
  47. }
  48. queue<int>Q;
  49.  
  50. int BFS(int S)
  51. {
  52. vst[S]=TRUE;
  53. dist[S]=0;
  54. int i,D=0;
  55.  
  56. int u,v;
  57. Q.push(S);
  58. while(!Q.empty())
  59. {
  60. u=Q.front();
  61. Q.pop();
  62.  
  63. for(i=1;i<=n;i++)
  64. {
  65. v=i;
  66. if(adj[u][v] && vst[v]!=TRUE)
  67. {
  68. vst[v]=TRUE;
  69. dist[v]=dist[u]+1;
  70. D=max(D,dist[v]);
  71. Q.push(v);
  72. }
  73. }
  74. }
  75. return D;
  76. }
  77.  
  78. int main()
  79. {
  80. //filer();
  81. int T,cas=0,i,j,k,u,v,x,y;
  82. scanf("%d",&n);
  83.  
  84. for(i=0;i<(n-1);i++)
  85. {
  86. scanf("%d%d",&u,&v);
  87. deg[u]++;
  88. deg[v]++;
  89. adj[u][v]++;
  90. adj[v][u]++;
  91. I.x=u;
  92. I.y=v;
  93. E.push_back(I);
  94. }
  95.  
  96. int E_sz=n-1;
  97. int ans=0;
  98. for(i=0;i<E_sz;i++)
  99. {
  100. x=0;y=0;
  101.  
  102. I=E[i];
  103. u=I.x;v=I.y;
  104. adj[u][v]--;
  105. adj[v][u]--;
  106.  
  107. deg[u]--;deg[v]--;
  108.  
  109. while(!PQ.empty())PQ.pop_back();
  110. TRUE++;
  111. for(j=1;j<=n;j++)
  112. {
  113. if(adj[u][j])
  114. {
  115. adj[u][j]--;
  116. adj[j][u]--;
  117. int ind=BFS(j);
  118. PQ.push_back(ind);
  119. adj[u][j]++;
  120. adj[j][u]++;
  121. }
  122. }
  123. sort(PQ.begin(),PQ.end(),cmp);
  124. for(j=0;j<=1 && j<PQ.size();j++)x+=(1+PQ[j]);
  125.  
  126. while(!PQ.empty())PQ.pop_back();
  127. TRUE++;
  128. for(j=1;j<=n;j++)
  129. {
  130. if(adj[v][j])
  131. {
  132. adj[v][j]--;
  133. adj[j][v]--;
  134. int ind=BFS(j);
  135. PQ.push_back(ind);
  136. adj[v][j]++;
  137. adj[j][v]++;
  138. }
  139. }
  140. sort(PQ.begin(),PQ.end(),cmp);
  141. for(j=0;j<=1 && j<PQ.size();j++)y+=(1+PQ[j]);
  142.  
  143. adj[u][v]++;
  144. adj[v][u]++;
  145.  
  146. deg[u]++;deg[v]++;
  147.  
  148. if((x*y)>ans)ans=x*y;
  149.  
  150. }
  151. printf("%d\n",ans);
  152. return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement