fork download 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define vi std::vector<int>
  5. #define isz(v) (int) v.size()
  6. #define pii std::pair<int, int>
  7. //#define int long long
  8. #define all(v) v.begin(), v.end()
  9. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. const int MAXN = 5e3 + 7;
  14. const int inf32 = 1e9 + 7;
  15.  
  16. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  17. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  18.  
  19. int n, f[MAXN][MAXN][2], par[MAXN], ans, cnt[MAXN];
  20. int t;
  21. vector<int> a[MAXN], g[MAXN];
  22.  
  23. void reset(){
  24.     ans = 0;
  25.     for(int i = 1; i <= n; i++)
  26.         for(int j = 1; j <= cnt[i]; j++) f[i][j][0] = f[i][j][1] = -inf32;
  27.     fill(cnt + 1, cnt + 1 + n, 0);
  28.     fill(par + 1, par + 1 + n , 0);
  29.     for(int i = 1; i <= n; i++)a[i].clear(), g[i].clear();
  30. }
  31.  
  32. void dfsBuild(int u, int p){
  33.     for(auto v : a[u]){
  34.         if(v == p) continue;
  35.         par[v] = u;
  36.         dfsBuild(v, u);
  37.     }
  38. }
  39.  
  40. void dfsDP(int u){
  41.     f[u][0][0] = f[u][0][1] = 0;
  42.     int sum = 0;
  43.  
  44.     for(int i = 1; i <= isz(g[u]) - 1; i++){
  45.         int v = g[u][i];
  46.         int las_v = g[u][i - 1];
  47.  
  48.         dfsDP(v);
  49.  
  50.         cnt[u] += cnt[v];
  51.         int maxi = 0;
  52.  
  53.         for(int cntU = 0; cntU <= cnt[u]; cntU++){
  54.             for(int cntV = 0; cntV <= min(cnt[v], cntU); cntV++){
  55.                 maximize(f[v][cntU][1], f[las_v][cntU - cntV][1] + f[v][cntV][0] + (cntU - cntV) * cntV),
  56.                 maximize(maxi, f[v][cntV][0] + cntV);
  57.  
  58.                 if(i == isz(g[u]) - 1) maximize(f[u][cntU][0], f[v][cntU][1]);
  59.  
  60.             }
  61.             if(u == 1) maximize(ans, f[u][cntU][0]);
  62.         }
  63.  
  64.         sum += maxi;
  65.  
  66.     }
  67.     maximize(cnt[u], 1);
  68.  
  69.     maximize(f[u][1][0], sum);
  70.     maximize(ans, f[u][1][0]);
  71.  
  72. }
  73.  
  74. signed main() {
  75.     ios::sync_with_stdio(false);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.  
  79. //    freopen("test.inp", "r", stdin);
  80. //    freopen("test.ans", "w", stdout);
  81.  
  82.     cin >> t;
  83.  
  84.     while(t--){
  85.  
  86.         reset();
  87.         f[0][0][1] = f[0][0][0] = 0;
  88.  
  89.         cin >> n;
  90.  
  91.         for(int i = 1; i <= n - 1; i++){
  92.             int x, y;
  93.             cin >> x >> y;
  94.             a[x].push_back(y);
  95.             a[y].push_back(x);
  96.             g[i].push_back(0);
  97.         } dfsBuild(1, -1), g[n].push_back(0);
  98.  
  99.         for(int i = 2; i <= n; i++) g[par[i]].push_back(i);
  100.         dfsDP(1);
  101.  
  102.         cout << ans << endl;
  103.  
  104.  
  105.     }
  106. //
  107. //    cerr << endl << "--------------------------" << endl;
  108. //    cerr << "Time: " << TIME << " s" << endl;
  109. //    cerr << "--------------------------" << endl;
  110.  
  111. }
  112.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Cu5aRN
language:
C++14 (gcc 8.3)
created:
14 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!