fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define N 200010
  6. #define pb push_back
  7. #define ll long long
  8. #define fs first
  9. #define sc second
  10. #define ii pair<int,int>
  11. #define iii pair<ii,int>
  12. #define matrix vector<vector<ll>>
  13.  
  14. ii dp[N][3];
  15. int n,u,v,q;
  16. vector<int>g[N];
  17.  
  18. ii SS(ii u,ii v)
  19. {
  20.     if(u.sc>v.sc)
  21.         return u;
  22.     if(u.sc<v.sc)
  23.         return v;
  24.     if(u.fs>v.fs)
  25.         return u;
  26.             else return v;
  27. }
  28.  
  29. ii SS2(ii u,ii v)
  30. {
  31.     if(u.fs+u.sc>v.fs+v.sc)
  32.         return u;
  33.             else return v;
  34. }
  35.  
  36. void DFS(int u,int p)
  37. {
  38.     for(auto v:g[u])
  39.         if(v!=p)
  40.             DFS(v,u);
  41.     //den
  42.     int cnt=0,S=0;
  43.     for(auto v:g[u])
  44.         if(v!=p)
  45.         {
  46.             S+=dp[v][0].fs+cnt*dp[v][0].sc;
  47.             cnt+=dp[v][0].sc;
  48.         }
  49.     dp[u][0]=max(dp[u][0],ii{S,cnt});
  50.     dp[u][1]=SS(dp[u][1],ii{S,cnt});
  51.     dp[u][2]=SS2(dp[u][2],ii{S,cnt});
  52.     cnt=0,S=0;
  53.     for(auto v:g[u])
  54.         if(v!=p)
  55.         {
  56.             S+=dp[v][1].fs+cnt*dp[v][1].sc;
  57.             cnt+=dp[v][1].sc;
  58.         }
  59.     dp[u][0]=max(dp[u][0],ii{S,cnt});
  60.     dp[u][1]=SS(dp[u][1],ii{S,cnt});
  61.      dp[u][2]=SS2(dp[u][2],ii{S,cnt});
  62.  
  63.     cnt=0,S=0;
  64.     for(auto v:g[u])
  65.         if(v!=p)
  66.         {
  67.             S+=dp[v][2].fs+cnt*dp[v][2].sc;
  68.             cnt+=dp[v][2].sc;
  69.         }
  70.     dp[u][0]=max(dp[u][0],ii{S,cnt});
  71.     dp[u][1]=SS(dp[u][1],ii{S,cnt});
  72.      dp[u][2]=SS2(dp[u][2],ii{S,cnt});
  73.     //trang
  74.     S=0;
  75.     for(auto v:g[u])
  76.         if(v!=p)
  77.             S+=dp[v][0].fs+dp[v][0].sc;
  78.     dp[u][0]=max(dp[u][0],ii{S,1});
  79.     dp[u][1]=SS(dp[u][1],ii{S,1});
  80.     dp[u][2]=SS2(dp[u][2],ii{S,1});
  81.     S=0;
  82.     for(auto v:g[u])
  83.         if(v!=p)
  84.             S+=dp[v][1].fs+dp[v][1].sc;
  85.     dp[u][0]=max(dp[u][0],ii{S,1});
  86.     dp[u][1]=SS(dp[u][1],ii{S,1});
  87.      dp[u][2]=SS2(dp[u][2],ii{S,1});
  88.  
  89.      S=0;
  90.     for(auto v:g[u])
  91.         if(v!=p)
  92.             S+=dp[v][2].fs+dp[v][2].sc;
  93.     dp[u][0]=max(dp[u][0],ii{S,1});
  94.     dp[u][1]=SS(dp[u][1],ii{S,1});
  95.     dp[u][2]=SS2(dp[u][2],ii{S,1});
  96. }
  97.  
  98. void xuli()
  99. {
  100.     cin>>n;
  101.     for(int i=1;i<=n;i++)
  102.         g[i].clear(),dp[i][0]=dp[i][1]=dp[i][2]={0,0};
  103.     for(int i=1;i<n;i++)
  104.     {
  105.         cin>>u>>v;
  106.         g[u].pb(v);
  107.         g[v].pb(u);
  108.     }
  109.     DFS(1,0);
  110.     cout<<max(max(dp[1][0].fs,dp[1][1].fs),dp[1][2].fs)<<"\n";
  111. }
  112.  
  113. int main()
  114. {
  115.  
  116.     ios::sync_with_stdio(0);
  117.     cin.tie(NULL);
  118.     cout.tie(NULL);
  119.     cin>>q;
  120.     while(q--)
  121.         xuli();
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 9496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Wp9UZh
language:
C++14 (gcc 8.3)
created:
3 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!