fork download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define gc getchar_unlocked
  4. #define pc putchar_unlocked
  5. #define PI (3.14159265)
  6. #define ff first
  7. #define ss second
  8. #define pb push_back
  9. #define MOD (1000000007LL)
  10. #define INF (100000005)
  11. #define SIZE (2)
  12. #define TREESIZE (302144)
  13. #define LEFT(n) (2*n)
  14. #define RIGHT(n) (2*n+1)
  15. #define epsilon 1e8 //add to double before casting to integer
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef pair<int, int> ii;
  22. typedef pair<ii, int> iii;
  23.  
  24.  
  25. #define N 100005
  26. int n;
  27. vector<int> adj[N];
  28.  
  29. ll ans = 0;
  30. ll distDown[N][3], distUp[N], subtreeDia[N];
  31.  
  32.  
  33. void dfs1(int, int);
  34. void dfs2(int, int);
  35. void dfs3(int, int);
  36.  
  37.  
  38. int main()
  39. {
  40.     ios_base::sync_with_stdio(0);
  41.     // freopen("input.txt", "r", stdin);
  42.  
  43.     cin>>n;
  44.     int e = n-1;
  45.     while(e--){
  46.         int a, b;
  47.         cin>>a>>b;
  48.  
  49.         adj[a].pb(b);
  50.         adj[b].pb(a);
  51.     }
  52.  
  53.  
  54.     //calculate 1st, 2nd and 3rd max distances from each vertex in its subtree
  55.     //and diameter if subtree of v
  56.     dfs1(1, -1);
  57.  
  58.     //calculate max dist from each vertex to vertices towards its parent, i.e. not in its subtree
  59.     dfs2(1, -1);
  60.  
  61.  
  62.     ans = 0;
  63.     //now for each vertex v, we assume it is a part of one of the diameters
  64.     //and that the other diameter lies in one of its subtrees
  65.     //find max of such products for all vertices
  66.     dfs3(1, -1);
  67.  
  68.     cout<<ans;
  69.     return 0;
  70. }
  71.  
  72.  
  73.  
  74. void dfs1(int v, int par){
  75.  
  76.  
  77.     distDown[v][0] = distDown[v][1] = distDown[v][2] = 0;
  78.     subtreeDia[v] = 0;
  79.  
  80.     for(int i=0;i<(int)adj[v].size();i++){
  81.  
  82.         int vv = adj[v][i];
  83.         if(vv == par)   continue;
  84.  
  85.         dfs1(vv, v);
  86.  
  87.         subtreeDia[v]  =max(subtreeDia[v], subtreeDia[vv]);
  88.         if(distDown[vv][0]+1 >= distDown[v][0]){
  89.  
  90.             distDown[v][2] = distDown[v][1];
  91.             distDown[v][1] = distDown[v][0];
  92.             distDown[v][0] = distDown[vv][0]+1;
  93.         }
  94.         else if(distDown[vv][0]+1 >= distDown[v][1]){
  95.  
  96.             distDown[v][2] = distDown[v][1];
  97.             distDown[v][1] = distDown[vv][0]+1;
  98.         }
  99.         else if(distDown[vv][0]+1 >= distDown[v][2]){
  100.  
  101.             distDown[v][2] = distDown[vv][0]+1;
  102.         }
  103.     }
  104.  
  105.     subtreeDia[v] = max(subtreeDia[v], distDown[v][0]+distDown[v][1]);
  106. }
  107.  
  108.  
  109. void dfs2(int v, int par){
  110.  
  111.     distUp[v] = 0;
  112.     if(par != -1){
  113.  
  114.         distUp[v] = max(distUp[v], 1 + distUp[par]);
  115.  
  116.         if(distDown[v][0]+1 == distDown[par][0])    distUp[v] = max(distUp[v], 1+distDown[par][1]);
  117.         else    distUp[v] = max(distUp[v], 1+distDown[par][0]);
  118.     }
  119.  
  120.     for(int i=0;i<(int)adj[v].size();i++){
  121.  
  122.         int vv = adj[v][i];
  123.         if(vv == par)   continue;
  124.  
  125.         dfs2(vv, v);
  126.     }
  127. }
  128.  
  129.  
  130. void dfs3(int v, int par){
  131.  
  132.     //we iterate through all children and assume other diameter in in the subtree of that child
  133.     for(int i=0;i<(int)adj[v].size();i++){
  134.  
  135.         int vv = adj[v][i];
  136.         if(vv == par)   continue;
  137.  
  138.         ll sd = subtreeDia[vv];
  139.         //now for the diameter involving v itself
  140.         //it has 2 ends and v is in the middle
  141.         //both ends can either be in subtree of v itself
  142.         //or one can be in subtree and other up towards its parent
  143.  
  144.         if(distDown[vv][0]+1 == distDown[v][0]){
  145.  
  146.             ll temp = sd * (distDown[v][1] + distDown[v][2]);
  147.             ans = max(ans, temp);
  148.  
  149.             temp = sd * (distDown[v][1] + distUp[v]);
  150.             ans = max(ans, temp);
  151.         }
  152.         else if(distDown[vv][0]+1 == distDown[v][1]){
  153.  
  154.             ll temp = sd * (distDown[v][0] + distDown[v][2]);
  155.             ans = max(ans, temp);
  156.  
  157.             temp = sd * (distDown[v][0] + distUp[v]);
  158.             ans = max(ans, temp);
  159.         }
  160.         else{
  161.  
  162.             ll temp = sd * (distDown[v][0] + distDown[v][1]);
  163.             ans = max(ans, temp);
  164.  
  165.             temp = sd * (distDown[v][0] + distUp[v]);
  166.             ans = max(ans, temp);
  167.         }
  168.  
  169.         dfs3(vv, v);
  170.     }
  171. }
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
Runtime error #stdin #stdout 0s 8544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N7gxhK
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!