cf581F 依赖背包+临时数组 好题

这题得加个临时数组才能做。。

/*

给定一棵树，树节点可以染黑白，要求叶子节点黑白平分

称连接黑白点的边为杂边，求使得杂边最少的染色方

那么设dp[i][j][0|1]表示i子树中有j个叶子节点，i染黑或白

那么其实是依赖背包，即枚举每个节点的字数v，进行分组即可

给dp初始化0x3f

边际条件：如果i是叶子节点，那么dp[i][i][0|1]=0;

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 5005

struct Edge{int to,nxt;}edge[maxn<<];

int n,k,flag[maxn],num[maxn],root,dp[maxn][maxn][],tot,head[maxn];

void init(){

    memset(head,-,sizeof head);

    tot++;

}

void addedge(int u,int v){

    edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;

}

int dfs1(int u,int pre){

    num[u]=;

    if(flag[u]==)return num[u]=;

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v!=pre)dfs1(v,u),num[u]+=num[v];

    }

    return num[u];

}

void dfs2(int u,int pre){

    if(flag[u]==){

        dp[u][][]=dp[u][][]=;

        return;

    }

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v!=pre)dfs2(v,u);

    }

    int tmp[maxn][];//临时数组，tmp[j]表示j个黑点的最小杂边

    dp[u][][]=dp[u][][]=;//这两种情况

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==pre)continue;

        memset(tmp,0x3f,sizeof tmp);

        for(int j=num[u];j>=;j--)

            for(int t=num[v];t>=;t--){

                tmp[j][]=min(tmp[j][],dp[u][j-t][]+min(dp[v][t][],dp[v][t][]+));

                tmp[j][]=min(tmp[j][],dp[u][j-t][]+min(dp[v][t][],dp[v][t][]+));

            }

        for(int j=num[u];j>=;j--)//每次更新完一次tmp数组都要更新到dp里

            dp[u][j][]=tmp[j][],dp[u][j][]=tmp[j][];

     }

}

int main(){

    cin>>n;

    int u,v;init();

    for(int i=;i<n;i++){

        cin>>u>>v;

        addedge(u,v);addedge(v,u);

        flag[u]++,flag[v]++;

    }

    if(n==){

        printf("%d\n",n-);

        return ;

    }

    memset(dp,0x3f,sizeof dp);

    root=;

    while(flag[root]==)root++;

    dfs1(root,);

    k=num[root]/;

    dfs2(root,);

    printf("%d\n",min(dp[root][k][],dp[root][k][]));

}