fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vl;
  12. typedef vector<pii> vii;
  13. typedef vector<pll> vll;
  14. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  15. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  16. #define all(x) (x).begin(),(x).end()
  17. #define pb push_back
  18. #define ff first
  19. #define ss second
  20. #define mp make_pair
  21.  
  22. const int N = 2e5 + 1;
  23. int podd[N], odw[N];
  24. vi graf[N], zb;
  25.  
  26. int wyn = 0;
  27.  
  28. void dfs_podd(int v, int ojc){
  29.     podd[v] = 1;
  30.     for(int u : graf[v]){
  31.         if(odw[u] || u == ojc) continue;
  32.         dfs_podd(u, v);
  33.         podd[v] += podd[u];
  34.     }
  35. }
  36.  
  37. int znajdz(int v, int ojc, int r){
  38.     for(int u : graf[v]){
  39.         if(odw[u] || u == ojc) continue;
  40.         if(podd[u] > r / 2) return znajdz(u, v, r);
  41.     }
  42.     return v;
  43. }
  44.  
  45. int zbierz(int v, int ojc, ll odl){
  46.     int nodl = odl + graf[v].size() - 2;
  47.     int w = nodl;
  48.     for(int u : graf[v]){
  49.         if(u == ojc || odw[u]) continue;
  50.         w = max(w, zbierz(u, v, nodl));
  51.     }
  52.     return w;
  53. }
  54.  
  55.  
  56. void decompose(int v){
  57.     dfs_podd(v, 0);
  58.     int r = podd[v];
  59.     int c = znajdz(v, 0, r);
  60.     int best = 0;
  61.     for(int u : graf[c]){
  62.         int akt = zbierz(u, c, 0);
  63.         wyn = max(wyn, akt + best + int(graf[c].size()));
  64.         best = max(akt, best);
  65.     }
  66.  
  67.     odw[c] = 1;
  68.     for(int u : graf[c]){
  69.         if(odw[u]) continue;
  70.         decompose(u);
  71.     }
  72.  
  73. }
  74.  
  75. int main(){
  76.     ios_base::sync_with_stdio(0);
  77.     cin.tie(0);
  78.  
  79.     int n; cin >> n;
  80.     for(int i = 1; i < n; i++){
  81.         int a, b; cin >> a >> b;
  82.         graf[a].pb(b); graf[b].pb(a);
  83.     }
  84.  
  85.     decompose(1);
  86.  
  87.  
  88.     cout << wyn << "\n";
  89.  
  90.  
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0.01s 9036KB
comments (?)
stdin
copy 
2
1 2
stdout
copy 
0
https://ideone.com/CZw62q
language:
C++ (gcc 8.3)
created:
19 hours ago
visibility:
public

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!