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

题意：给定一棵树,第i个结点有 权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )
分析:

• 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp.
• 表示以第i个结点为根节点的子树满足最长链小于等于l. 那么我们考虑如何转移.对于当前节点x而言,我们定义 表示删除当前节点的子树满足最长链小于等于l-1的方案的最小值,显然
  .
• 那么考虑 如何转移,都是保留x节点的方案，那么当前子树的最长链有可能是某两个子节点的最长链和当前节点合并产生---------(当前第一个子节点最长链那么另一个子节点就需要是)，而且对于子节点最长链必须要小于 才能转移，所以只取 进行转移.
• 第二种情况就是当前子树最长链只是某个子节点的最长链加上当前节点，那么和第一种情况类似，下标也是只取进行转移.

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e3+10;

int head[maxn<<1],to[maxn<<1],nxt[maxn<<1];
int cnt,n,l,dp[maxn][maxn],a[maxn];

void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}

void add( int u,int v )
{
    nxt[cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt++;
} 

void dfs( int x,int f )
{
    dp[x][0]=a[x];
    for( int i=head[x];~i;i=nxt[i] )
    {
        int v=to[i];
        if( v==f ) continue;
        dfs(v,x);
        dp[x][0]+=dp[v][l-1];
    }
    for( int i=1;i<l;i++ )
    {
        int tmp=0;
        for( int j=head[x];~j;j=nxt[j] )
        {
            int v=to[j];
            if( v==f ) continue;
            dp[x][i]=min(tmp+dp[v][i-1],dp[x][i]+dp[v][min(i-1,l-i-1)] );
            tmp+=dp[v][min(i-1,l-i-1)];
        }
        dp[x][i]=min(dp[x][i],dp[x][i-1]);;
    }

}

int main()
{
    scanf("%d%d",&n,&l);init();
    for( int i=1;i<=n ;i++ ) scanf("%d",&a[i]);
    for( int i=1,u,v;i<n;i++ )
    {
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    printf("%d\n",dp[1][l-1]);
    return 0;
}