*工作~

题目链接

题意概述:

给定一棵树,除根外每个点有一个权值,求选 $k$ 个点后权值最大和,要求一个点被选,那么他的祖先必须被选.

思路:

简单 $n^3$ 次方 $dp$ 一下,n<=100怎末跑都能过,从根节点向下深搜一边,对于一个点 $x$,枚举他的每个儿子,总共选几个点和当前儿子选几个点.

注意:

• 枚举总共选几个点时,必须先选自己(除根结点不能选自己),并且选取个数不可超过当前节点总个数 $siz[x]$.
• 在枚举当前儿子选几个点时,必须保证 $p-z>=siz[x]-siz[y]$ ,即剩下p-z个数要选够.选的个数还要小于当前儿子拥有节点个数(不加也没关系,会判成负无穷).

重点:

在枚举选几个儿子时需倒序枚举,不然一个权值较大的节点会被计算多次.类似于01背包变成了完全背包.(我刚开始无脑码的时候就在这儿掉坑了)

code

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,k;
int c[N];
int fr[N],to[N],nxt[N],too=0;
int f[N][N];
int dep[N],siz[N];
void add(int x,int y)
{
    if(!y) return;
    to[++too]=y;
    nxt[too]=fr[x];
    fr[x]=too;
}
void dfs(int x)
{
    f[x][1]=c[x];
    siz[x]=1;
    for(int i=fr[x];i;i=nxt[i])
    {
        int y=to[i];
        dfs(y);
        siz[x]+=siz[y];
        for(int p=min(k,siz[x]);p>=2;p--)
        for(int z=max(1,p+siz[y]-siz[x]);z<=p-1;z++)
        f[x][p]=max(f[x][p],f[x][p-z]+f[y][z]);
    }
}
int main()
{
    cin>>n>>k;
    memset(f,-0x3f,sizeof(f));
    for(int i=2;i<=n;i++)
    scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(i,x);add(i,y);
    }
    siz[1]=0;
    f[1][0]=0;
    for(int i=fr[1];i;i=nxt[i])
    {
        int y=to[i];
        dfs(y);
        siz[1]+=siz[y];
        for(int p=min(k,siz[1]);p>=1;p--)
        for(int z=max(1,p+siz[y]-siz[1]);z<=p;z++)
        f[1][p]=max(f[1][p],f[1][p-z]+f[y][z]);
    }
    cout<<f[1][k]<<endl;
}