fork download
copy 
  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.     memset(f, -0x3f, sizeof(f));
  26.     fill(cnt + 1, cnt + 1 + n, 0);
  27.     fill(par + 1, par + 1 + n , 0);
  28.     for(int i = 1; i <= n; i++)a[i].clear(), g[i].clear();
  29. }
  30.  
  31. void dfsBuild(int u, int p){
  32.     for(auto v : a[u]){
  33.         if(v == p) continue;
  34.         par[v] = u;
  35.         dfsBuild(v, u);
  36.     }
  37. }
  38.  
  39. void dfsDP(int u){
  40.     f[u][0][0] = f[u][0][1] = 0;
  41.     int sum = 0;
  42.  
  43.     for(int i = 1; i <= isz(g[u]) - 1; i++){
  44.         int v = g[u][i];
  45.         int las_v = g[u][i - 1];
  46.  
  47.         dfsDP(v);
  48.  
  49.         cnt[u] += cnt[v];
  50.         int maxi = 0;
  51.  
  52.         for(int cntU = 0; cntU <= cnt[u]; cntU++){
  53.             for(int cntV = 0; cntV <= min(cnt[v], cntU); cntV++){
  54.                 maximize(f[v][cntU][1], f[las_v][cntU - cntV][1] + f[v][cntV][0] + (cntU - cntV) * cntV),
  55.                 maximize(maxi, f[v][cntV][0] + cntV);
  56.             }
  57.             if(i == isz(g[u]) - 1) maximize(f[u][cntU][0], f[v][cntU][1]);
  58.             if(u == 1) maximize(ans, f[u][cntU][0]);
  59.         }
  60.         sum += maxi;
  61.  
  62.     }
  63.     maximize(cnt[u], 1);
  64.     maximize(f[u][1][0], sum);
  65.  
  66.     if(u == 1) maximize(ans, f[u][1][0]);
  67.  
  68. }
  69.  
  70. signed main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.  
  75.     cin >> t;
  76.  
  77.     while(t--){
  78.  
  79.         reset();
  80.         f[0][0][0] = 0;
  81.  
  82.         cin >> n;
  83.  
  84.         for(int i = 1; i <= n - 1; i++){
  85.             int x, y;
  86.             cin >> x >> y;
  87.             a[x].push_back(y);
  88.             a[y].push_back(x);
  89.             g[i].push_back(0);
  90.         } dfsBuild(1, -1), g[n].push_back(0);
  91.  
  92.         for(int i = 2; i <= n; i++) g[par[i]].push_back(i);
  93.         dfsDP(1);
  94.  
  95.         cout << ans << endl;
  96.  
  97.     }
  98.  
  99. }
  100.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JElU6h
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!