树形DP学习总结

AH20 · 2022-08-19 15:24:13 · 个人记录

树形DP学习总结

首先我们来看几个概念：

最大独立集：从图中取尽可能多的点来组成一个集合，使得该集合中任意两点没有边相连
最小点覆盖：从图中取尽可能少的点来组成一个集合，使得原图中的所有边都至少有一个点在该集合中
最小支配集：从图中取尽可能少的点来组成一个集合，使得剩余的点都与取出的点有连边

我们来分别讨论这几个问题。其中，在一颗树上，最小点覆盖和最小支配集的大小并不是是等价的(如1-2-3-4,最小点覆盖只能是\{2,3\},但最小支配集可以是\{2,3\}或者\{1,4\}，在6个点的链中，最小支配集和最小点覆盖的大小也不等价)

最大独立集

例题：

没有上司的舞会

解题思路

设dp[i][0]为这个人没有去参加舞会时他的子树中参加舞会最多的人数，dp[i][1]为这个人去参加舞会时他的子树中参加舞会最多的人数。转移方程为

\begin{aligned} &dp[i][0]=\sum max(dp[k][0],dp[k][1]),k \in son_i \\ &dp[i][1]=\sum dp[k][0],k \in son_i \\ \end{aligned}

解题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//dp[i][1]表示这个人参会时的最大值
//dp[i][0]表示这个人没有参会时的最大值
//则dp[i][1]=dp[fa[i]][0]+a[i]
//dp[i][0]=max(dp[fa[i]][1],dp[fa[i]][0])
//我们从根节点开始递归
const ll maxm=6005;
struct node{
    vector<ll>son;
    ll fa;
};
node all[maxm];
ll a[maxm];
ll dp[maxm][3];
ll inc[maxm];
void solve(ll now){
    inc[all[now].fa]--;
    for(auto i:all[now].son){
        dp[now][1]+=dp[i][0];
        dp[now][0]+=max(dp[i][0],dp[i][1]);
    }
    dp[now][1]+=a[now];
    if(all[now].fa==0) return;
    if(inc[all[now].fa]==0) solve(all[now].fa);
}
int main(){
    ll n,i,j;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) all[i].fa=0;
    for(i=1;i<n;i++){
        ll L,K;
        scanf("%lld%lld",&L,&K);
        all[L].fa=K;
        all[K].son.push_back(L);
        inc[K]++;
    }
    for(int i=1;i<=n;i++){
        if(all[i].son.empty()) solve(i);
    }
    ll ans;
    for(int i=1;i<=n;i++){
        if(all[i].fa==0) ans=max(dp[i][1],dp[i][0]);
    }
    cout<<ans;
    return 0;
}

最小支配集

例题

Cell Phone Network G

解题思路

设dp[i][0]为被自己覆盖，dp[i][1]为被自己的儿子覆盖，dp[i][2]为被自己的父亲覆盖，则状态转移方程可以写为：

\begin{aligned} & dp[i][0]=1+\sum min(dp[k][0],dp[k][1],dp[k][2]),k \in son_i \\ & dp[i][2]=\sum min(dp[k][0],dp[k][1]),k \in son_i \\ & dp[i][1]=\sum min(dp[k][0],dp[k][1])+dp[spi][0],k,spi \in son_i \end{aligned}

其中spi为i的满足dp[k][0]-dp[k][1]最小的儿子，即在保证答案最小的前提下有i必有一个儿子在支配集中

解题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll dp[10005][3];
const ll inf=1e9+7;
//dp[0] 自己有
//dp[1] 被自己的儿子覆盖
//这个儿子应该满足
//dp[2] 被自己的父亲覆盖
//被自己的儿子节点覆盖的状态转移方程是什么？
vector<ll>edge[10005];
void dfs(ll now,ll fa){
    if(edge[now].size()==1&&edge[now][0]==fa){
        dp[now][0]=1;
        dp[now][1]=1;
        dp[now][2]=0;
        //这道题在初始化的时候需要注意一点，叶子节点不能被自己的儿子覆盖！！！
        return;
    }
    ll sp=inf,spi;
    for(auto i:edge[now]){
        if(i==fa) continue;
        dfs(i,now);
        if(dp[i][0]-dp[i][1]<sp) sp=dp[i][0]-dp[i][1],spi=i;
        dp[now][0]+=min(dp[i][0],min(dp[i][1],dp[i][2]));
        dp[now][2]+=min(dp[i][0],dp[i][1]);
    }
    for(auto i:edge[now]){
        if(i==fa) continue;
        if(i==spi){
            dp[now][1]+=dp[i][0];
            continue;
        }
        dp[now][1]+=min(dp[i][0],dp[i][1]);
    }
    dp[now][0]++;
}
int main(){
     ll i,j;
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        ll from,to;
        scanf("%lld%lld",&from,&to);
        edge[from].push_back(to);
        edge[to].push_back(from);
    }
    dfs(1,-1);
    cout<<min(dp[1][1],dp[1][0])<<endl;
    return 0;
}

最小点覆盖

例题

Strategic game

解题思路

设dp[i][0]为当i点没有卫兵时i的子树中的所有路径被完全覆盖时需要的最少人数，dp[i][1]为i点有卫兵时需要的最小人数，我们可以得到以下转移方程：

\begin{aligned} &dp[i][0]=\sum dp[k][1],k \in son_i \\ &dp[i][1]=1+\sum min(dp[k][0],dp[k][1]),k \in son_i \\ \end{aligned}

解题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll n;
char s[80];
vector<ll>edge[1501];
ll dp[1501][2];
void init(){
    for(int i=1;i<=n;i++) edge[i].clear(),dp[i][0]=dp[i][1]=0;
}
void dfs(int now,int fa){
         if(edge[now].size()==1&&fa!=-1){
            dp[now][1]=1;
            dp[now][0]=0;
            return;
         }
         for(auto i:edge[now]){
            if(i==fa) continue;
            dfs(i,now);
            dp[now][1]+=min(dp[i][0],dp[i][1]);
            dp[now][0]+=dp[i][1];
         }
         dp[now][1]++;
}
void solve(){
    init();
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        ll num=0;
        ll now=0;
        for(int j=1;j<=strlen(s+1);j++){
            if(s[j]==':') break;
            now*=10,now+=s[j]-'0';
            s[j]='*';
        }
        now++;
        for(int j=1;j<=strlen(s+1);j++){
            if(s[j]>='0'&&s[j]<='9'&&j>1) num*=10,num+=s[j]-'0';
        }
        for(int j=1;j<=num;j++){
            ll v;
            scanf("%lld",&v);v++;
            edge[v].push_back(now);
            edge[now].push_back(v);
        }
    }//建树完成
    dfs(1,-1);
    printf("%lld\n",min(dp[1][0],dp[1][1]));
}
int main(){
    while(~scanf("%lld",&n)) solve();
    return 0;
}