YEZAELP

o58_oct_c1_bypass

Nov 29th, 2021 (edited)
151
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. using pl = pair <lli, lli>;
  6. const lli INF = 1e18;
  7. const lli N = 1e5 + 10;
  8. vector <lli> g[N];
  9. vector <pl> edge;
  10. lli node[N], level[N], mx1[N], mx2[N], mx1idx[N];
  11. bool vs[N];
  12. lli n;
  13.  
  14. lli dfs(lli u, lli p, lli lvl){
  15.     if(vs[u]) return node[u];
  16.     vs[u] = true;
  17.     node[u] = 1;
  18.     level[u] = lvl;
  19.     for(auto v: g[u]){
  20.         if(v != p){
  21.             node[u] += dfs(v, u, lvl + 1);
  22.             if(node[v] > mx1[u]){
  23.                 mx2[u] = mx1[u];
  24.                 mx1[u] = node[v];
  25.                 mx1idx[u] = v;
  26.             }
  27.             else if(node[v] > mx2[u]){
  28.                 mx2[u] = node[v];
  29.             }
  30.         }
  31.     }
  32.     return node[u];
  33. }
  34.  
  35. int main(){
  36.     cin >> n;
  37.     for(lli i=1;i<=n-1;i++){
  38.         lli u, v;
  39.         cin >> u >> v;
  40.         g[u].push_back(v);
  41.         g[v].push_back(u);
  42.         edge.push_back({u, v});
  43.     }
  44.  
  45.     dfs(1, 0, 1);
  46.  
  47.     lli mx = 0;
  48.     for(auto uv: edge){
  49.         lli u = uv.first;
  50.         lli v = uv.second;
  51.         if(level[u] > level[v]) swap(u, v);
  52.         lli a = n - node[u], b = 0;
  53.         if(mx1idx[u] == v) a = max(a, mx2[u]);
  54.         else a = max(a, mx1[u]);
  55.         b = max(b, mx1[v]);
  56.         mx = max(mx, (lli)(a * b));
  57.     }
  58.  
  59.     cout << mx;
  60.  
  61.     return 0;
  62. }
RAW Paste Data Copied