动态规划、树形动态规划

会做的题赛时想不出来跑去写 H 的随机矩阵假做法，我是不是飞舞？

首先设计 $dp_{i,0}$ 为没有保护 $i$ 点时以节点 $i$ 为根的子树的答案，$dp_{i,1}$ 为保护了 $i$ 点时以节点 $i$ 为根的子树的答案。

对于 $dp_{i,0}$，因为没选点 $i$，每个孩子是否选择不影响计算答案。对于 $dp_{i,1}$，枚举选择的孩子数量，优先选择对答案贡献更大的孩子转移。实际上就是把 $i$ 的所有孩子节点 $x$ 按照 $dp_{x,1} - dp_{x,0}$ 的值从大到小排序后枚举选择的孩子数量转移。

使用 $m_i$ 表示 $i$ 的孩子数量，$son_{i,j}$ 表示节点 $i$ 的第 $j$ 个孩子（排序后）能够写出状态转移方程。这里的 $c,a_i$ 和题目中的意义相同。

$$dp_{i,0}= \sum\limits_{j=1}^{m_i} \max(dp_{son_{i,j},0},dp_{son_{i,j},1})$$

$$dp_{i,1}= \max\limits_{j=0}^{m_i}\left( \sum\limits_{k=1}^{j} dp_{son_{i,k},1} + \sum\limits_{k=j+1}^{m_i} dp_{son_{i,k},0} - 2 \times c \times j + a_i \right)$$

使用前缀和优化 $dp_{i,1}$ 的转移。以节点 $1$ 为根进行树形动态规划，答案为 $\max(dp_{1,0},dp_{1,1})$。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
long long c,dp[200'005][2];
vector<int> v[200'005];
int n,a[200'005];
void dfs(int x,int las){
    for(int i:v[x]) if(i!=las) dfs(i,x);
    sort(v[x].begin(),v[x].end(),[&](auto x,auto y){
        return dp[x][1]-dp[x][0]>dp[y][1]-dp[y][0];
    });
    for(int i:v[x]) if(i!=las) dp[x][0]+=max(dp[i][0],dp[i][1]);
    long long cnt=0ll,pre=0ll,suf=0ll;
    for(int i:v[x]) if(i!=las) suf+=dp[i][0];
    dp[x][1]=pre+suf+a[x];
    for(int i:v[x]) if(i!=las){
        ++cnt,pre+=dp[i][1],suf-=dp[i][0];
        dp[x][1]=max(dp[x][1],pre+suf-2*c*cnt+a[x]);
    }
}
void solution(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n-1;i++){
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout<<max(dp[1][0],dp[1][1])<<'\n';
    for(int i=1;i<=n;i++) dp[i][0]=0ll,dp[i][1]=0ll,v[i].clear();
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}