dinnerhunt

牛牛学习了树。

给出一棵节点数为 n 的树，删去一个点 i 的代价为 $a_i$，一条链的长度定义为路径上 点 的个数。一棵树死了，满足不存在一条长度 $\geq l$ 的链，牛牛希望用最少代价杀死这棵树。

链接 🔗

「NowCode」杀树

题解 ❓

树型DP

代码

const int N = 5e3+10;
V G[N];
ll a[N],dp[N][N],s[N],sz[N],n,m;
void dfs(ll x,ll fa)
{
    sz[x] = 1;
    dp[x][1] = dp[x][0] = 0;
    for(auto v: G[x])
    {
        if(v == fa) continue;
        dfs(v,x);
        ll now = 1e18;
        FOR(i,0,sz[v])
        {
            if(i >= m) break;
            now = min(now,dp[v][i]);
        }
        dp[x][0] += now;
        FOR(i,1,sz[x]+sz[v]) s[i] = 1e18;
        FOR(i,1,sz[x])if(i < m)
            FOR(j,0,sz[v]) if(i+j<m)
                s[max(i,j+1)] = min(s[max(i,j+1)],dp[x][i] + dp[v][j]);
        sz[x]+= sz[v];
        FOR(i,1,sz[x]) dp[x][i] = s[i];
    }
    dp[x][0] += a[x];
}
int main()
{
//    __IN;__OUT;
    RLL2(n,m);
    FOR(i,1,n) RLL(a[i]);
    FOR(i,1,n-1)
    {
        ll x,y;RLL2(x,y);
        G[x].pb(y); G[y].pb(x);
    }
    MM(dp,233);
    dfs(1,1);
    ll ans = dp[1][0];
    FOR(i,1,m-1)  ans = min(ans,dp[1][i]);
    PLN(ans);
    return 0;
}