牛客IOI周赛16-普及组 D 杀树

• 树形dp
• $dp[i][j]$表示以第$i$个点为根的子树中以$i$为端点的最长链小于等于$j$时的最小代价。
• 以1为根进行深度优先遍历，枚举以当前点为端点的最长链的长度$j$,显然$0 \leq j \leq l-1$,此时一定有一颗子树的以根为端点的最长链长度为$j-1$,其余的为$ \min (j-1,l-j-1)$,这里可以dp一下求最小值。
• 注意当$j$取0时表示删除当前点,$dp[i][0] = \sum_{k \in son(i)}dp[k][l-1]$

代码:

#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i = (a);i <= (b);++i)
typedef long long ll;
const int maxn = 5000+5;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res = 1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}}
struct graph
{
    int head[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],sz;
    void init(){memset(head,-1,sizeof(head));}
    graph(){init();}
    void push(int a,int b,int c){nxt[sz]=head[a],to[sz]=b,w[sz]=c,head[a]=sz++;}
    int& operator[](const int a){return to[a];}
}g;
int dp[maxn][maxn],a[maxn];
int n,k;
//dp[i][j]--以第i个点为根的子树中以i为端点的最长链小于等于j时的最小代价。
void dfs(int now,int pre)
{
    dp[now][0]=a[now];
    for(int i = g.head[now];~i;i = g.nxt[i]){
        if(g[i]==pre)continue;
        dfs(g[i],now);
        dp[now][0]+=dp[g[i]][k-1];
    }
    for(int i = 1;i < k;++i){
        int tmp = 0;
        for(int j = g.head[now];~j;j = g.nxt[j]){
            if(g[j]==pre)continue;
            dp[now][i]=min(tmp+dp[g[j]][i-1],dp[now][i]+dp[g[j]][min(i-1,k-i-1)]);
            tmp+=dp[g[j]][min(i-1,k-i-1)];
        }
        dp[now][i]=min(dp[now][i],dp[now][i-1]);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("simple.in","r",stdin);
    freopen("simple.out","w",stdout);
#endif
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
    for(int i = 1,a,b;i < n;++i){
        scanf("%d%d",&a,&b);
        g.push(a,b,0);
        g.push(b,a,0);
    }
    dfs(1,0);
    cout<<dp[1][k-1]<<endl;
    return 0;
}