题解：CF1988D The Omnipotent Monster Killer

Daniel_yao · 2024-07-25 10:01:32 · 题解

Solve

第一眼有点像最大独立集，可以考虑往这方面想。

由于有了回合的限制，所以在 dp 时要多加一维来除去回合的后效性。设 dp_{x,y} 表示第 x 个点在 y 回合被选中带来的最小贡献。很显然初始状态 dp_{x,y}=a_x\times y。

转移也很显然，父亲和儿子不能在同一回合被选中，所以只需要在 dfs 中枚举所有回合，然后把所有不同回合的儿子状态取最小贡献，转移至父亲即可。

考虑回合数，因为每一次选点会将树拆成森林，然后每一个小树又会减半，继续分。所以可以证明回合数在 \log n 量级。

所以转移与计算贡献加上总时间复杂度 O(n \log^2 n)，可以通过此题。

Code

#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define inf 1e18

using namespace std;

const int N = 3e5 + 10;

struct Node {
  int v, nx;
} e[N << 1];

int T, n, a[N], h[N], dp[N][25], tot, m, sum, ans = inf;

void add(int u, int v) {
  e[++tot] = (Node){v, h[u]};
  h[u] = tot;
}

void dfs(int x, int fa) {
  for (int i = h[x]; i; i = e[i].nx) {
    int y = e[i].v;
    if(y == fa) continue;
    dfs(y, x);
  }
  if(x == 1) return ;
  For(i,1,m) {
    int num = inf;
    For(j,1,m) {
      if(i == j) continue;
      num = min(num, dp[x][j]);
    }
    dp[fa][i] += (num == inf ? 0 : num); 
  }
}

void solve() {
  ans = inf; sum = tot = 0;
  For(i,1,n) h[i] = 0;
  cin >> n;
  For(i,1,n) cin >> a[i], sum += a[i];
  For(i,1,n-1) {
    int u, v;
    cin >> u >> v;
    add(u, v), add(v, u);
  }
  m = (int)ceil(log2(n))+1;
  For(i,1,n) For(j,1,m) dp[i][j] = a[i] * j;
  dfs(1, 0);
  For(i,1,m) ans = min(ans, dp[1][i]);
  cout << ans << '\n';
  return ;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> T;
  while(T--) solve();
  return 0;
}