20南京站M题(树上dp)、19南京站J题(KM算法)+思维

M. Monster Hunter

树上背包。对于父节点和子节点，都是可选可不选，删除的点是任意的，但要满足价值最小。 状态设计： dp[u][num][0]表示以u为根节点(不包含自身)，选择num个子节点，能获取的最小价值。 dp[u][num][1]表示以u为根节点(包含自身)，选择num个子节点，能获取的最小价值。

状态转移：f[u][i+j][0]=min(f[u][i+j][0],f[u][i][0]+min(f[v][j][0],f[v][j][1])); u结点不选被删掉，因此子节点并不对父节点产生额外的的贡献。 相反，f[u][i+j][1]=min(f[u][i+j][1],f[u][i][1]+min(f[v][j][0],f[v][j][1]+hp[v])); u结点被选择，子节点的权值会被父节点累加上。

实现：双重循环枚举出u和v不同的取值，从后向前，滚动更新。

#include 
#define int long long
#define ios cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
#define endl '\n'
#define ULL unsigned long long
#define down 0.996
using namespace std;
const double eps=1e-8;
const double inf=1e18;
const int mod=998244353;
const int P=131;
const int N=3e3+5;
int n,a[N],hp[N],f[2005][2005][2],sz[N];
vectore[N];
void dfs(int u,int fa)
{
    f[u][1][1]=hp[u],f[u][0][0]=0;
    sz[u]=1;
    for(int v:e[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        for(int i=sz[u];i>=0;i--)
        {
            for(int j=sz[v];j>=0;j--)
            {
                f[u][i+j][0]=min(f[u][i+j][0],f[u][i][0]+min(f[v][j][0],f[v][j][1]));
                f[u][i+j][1]=min(f[u][i+j][1],f[u][i][1]+min(f[v][j][0],f[v][j][1]+hp[v]));
            }
        }
        sz[u]+=sz[v];
    }
}
void solve()
{
    cin>>n;
    for(int i=0;ix;
        e[i].push_back(x);e[x].push_back(i);
    }
    for(int i=1;i>hp[i];
    for(int i=0;i