fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define int long long
  7. typedef pair<int,int> pii;
  8. const int MAXN = 3e5 +5;
  9. int n, ans, sizes[MAXN], dp[MAXN];
  10. vector <int> adj[MAXN];
  11.  
  12. void dfs1(int x, int pa){
  13.    sizes[x] = 1;
  14.    dp[x] =0;
  15.    for (auto i: adj[x]){
  16.        if(i == pa) continue;
  17.        dfs1(i, x);
  18.        sizes[x] += sizes[i];
  19.        dp[x] += dp[i] + sizes[i];
  20.    }
  21. }
  22.  
  23. void dfs2(int x, int pa, int len){
  24.     ans = max(ans, dp[x] + len);
  25.     for (auto i : adj[x]){
  26.         if ( i == pa) continue;
  27.         int len2 = len + (dp[x] - dp[i] - sizes[i] +  (n-sizes[i]));
  28.         dfs2(i, x, len2);
  29.     }
  30. }
  31. signed main(){
  32.     cin >> n;
  33.     for (int i =1; i <=n-1; i++){
  34.         int x, y;
  35.         cin >> x >> y;
  36.         adj[x].push_back(y);
  37.         adj[y].push_back(x);
  38.     }
  39.  
  40.     dfs1(1,0);
  41.     dfs2(1,0,0);
  42.     cout << ans+n;
  43. }
Success #stdin #stdout 0.01s 14428KB
comments (?)
stdin
copy 
5
1 2
1 3
2 4
2 5
stdout
copy 
14
https://ideone.com/OBAzaL
language:
C++ (gcc 8.3)
created:
10 days 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!