fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  4. #define start_routine() int begtime = clock();
  5. #define end_routine() int endtime = clock(); \
  6.                       cerr << "\n\n" << "Time elapsed: " << \
  7.                       (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
  8.                       return 0
  9. #define ll long long int
  10. #define ull unsigned long long int
  11. #define db long double
  12. #define ff first
  13. #define ss second
  14. #define mp make_pair
  15. #define pb push_back
  16. #define lb lower_bound
  17. #define ub upper_bound 
  18. #define pii pair<int , int>
  19. #define pdd pair<db , db>
  20. #define pll pair<ll , ll>
  21. #define vpl vector<pll >
  22. #define vll vector<ll >
  23. #define mod 1000000007
  24. #define mod1 998244353 
  25. #define inf 1000000000000000007
  26. #define eps 0.000001
  27. #define stp fixed<<setprecision(20)
  28. #define endl '\n'
  29.  
  30. #pragma comment(linker, "/stack:200000000")
  31. #pragma GCC optimize("Ofast")
  32. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  33.  
  34. const ll N=500005;
  35.  
  36. vll adj[N],v[N];
  37. ll d[N],f[N],s[N];
  38. ll n;
  39.  
  40. bool cmp(ll a,ll b)
  41. {
  42.     return f[a]<f[b];
  43. }
  44.  
  45. void dfs(ll x,ll pr)
  46. {
  47.     s[x]=1;
  48.     for(auto i:adj[x])
  49.         if(i!=pr)
  50.             dfs(i,x);
  51.  
  52.     for(auto i:adj[x])
  53.         if(i!=pr)
  54.             s[x]+=s[i];
  55.  
  56.     d[x]=s[x]*s[x];f[x]=d[x];
  57.     for(auto i:adj[x])
  58.         if(i!=pr)
  59.             d[x]=min(d[x],d[i]+(s[x]-s[i])*(s[x]-s[i]));
  60.  
  61.     f[x]+=d[x]-2*n*s[x];
  62.     for(auto i:adj[x])
  63.         if(i!=pr)
  64.             v[x].pb(i);
  65. }
  66.  
  67. int main()
  68. {
  69.     fastio;
  70.     #ifdef APNA_IO
  71.         start_routine();
  72.         freopen("input.txt", "rt", stdin);
  73.         freopen("output.txt", "wt", stdout);    
  74.     #endif
  75.  
  76.     cin>>n;
  77.     for(ll i=1;i<n;i++)
  78.     {
  79.         ll x,y;cin>>x>>y;
  80.         adj[x].pb(y);
  81.         adj[y].pb(x);
  82.     }
  83.  
  84.     dfs(1,1);ll ans=0;
  85.     for(ll i=1;i<=n;i++)
  86.     {
  87.         sort(v[i].begin(), v[i].end(),cmp);
  88.  
  89.         if(v[i].size()==0) continue;
  90.         if(v[i].size()==1) ans=min(ans,f[i]);
  91.         if(v[i].size()>1)
  92.         {
  93.             ll x=v[i][0],y=v[i][1];
  94.             ll val=f[x]+f[y]+2*s[x]*s[y];
  95.             ans=min(ans,val);
  96.         }
  97.     }
  98.  
  99.     ll val=n*(n-1);
  100.     cout<<(val-ans)/2;
  101.  
  102.     #ifdef APNA_IO
  103.         end_routine();  
  104.     #endif
  105. }
Success #stdin #stdout 0s 50392KB
comments (?)
stdin
copy 
35
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
1 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
1 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
stdout
copy 
1018
https://ideone.com/kPEg0m
language:
C++14 (gcc 8.3)
created:
5 years 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!