CF1988D The Omnipotent Monster Killer

luogu中文题面：https://www.luogu.com.cn/problem/CF1988D

树形dp。我们只关心子树的根节点v什么时候被删去。dp[u][i]+= min(dp[v][1...i-1,i+1...T]). T是log(n)的。
因为\(T\leq Mex(u)\), 而考虑要多少节点使\(Mex(u)=T\),有\(f_T = 1 + f_1 + ... f_{T-1}\)得\(T=log_2n\)

不会证明复杂度，所以T开大了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 3e5 + 11;
LL dp[N][201], a[N], suf_mi[222], pre_mi[222];
int n;
vector<int> G[N];
void dfs(int u, int fa){
  dp[u][0] = 1e18;
  for(int i = 1;i <= 200; i++)dp[u][i] = 1ll * a[u] * i;
  for(int v : G[u]){
    if(v == fa)continue;
    dfs(v, u);
    pre_mi[0] = suf_mi[201] = 1e18;
    for(int i = 1;i <= 200; i++)pre_mi[i] = min(pre_mi[i-1], dp[v][i]);
    for(int i = 200;i >= 1; i--)suf_mi[i] = min(suf_mi[i+1], dp[v][i]);
    for(int i = 1;i <= 200; i++){
      LL res = 1e18;
      if(i > 1)res = pre_mi[i-1];
      if(i < 200)res = min(res, suf_mi[i+1]);
      dp[u][i] += res;
    }
  }
}
void work(){
  cin>>n;
  for(int i = 1;i <= n; i++){
    scanf("%lld", &a[i]);
    G[i].clear();
  }
  for(int i = 1;i < n; i++){
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 1);
  LL res = 1e18;
  for(int i = 0;i <= 200; i++){
    res = min(res, dp[1][i]);
  }
  cout<<res<<endl;
}
int main(){
  int T;
  cin>>T;
  while(T--)work();
  return 0;
}