UVA1220 题解

· · 题解

树形dp问题。

类似题P1352 没有上司的舞会

如果想了解更多树形 dp ，你可以点这里link

solution

这题就是在求最大独立集问题的基础上加了一个唯一性判断。

我们可以用 dp 数组求解最大独立集，同时新开一个 f 数组判断唯一性。

树形 dp 的题一般都会把子树的规模定义成一维状态，因为树形 dp 有很明显的层次性，只有孩子的值求出之后才能转移到父亲。

我们定义 dp[i][0/1] 表示以 i 为根的子树能选到的最大独立集， 0 代表当前节点不选， 1 代表当前节点选。

同时定义 f[i][0/1] ，下标意义同上，代表唯一性。

先考虑最大独立集问题：

那么，如果一个节点的父亲选了，那么孩子一定不能选。

如果父亲没有选，那么孩子可选可不选，取最大值。

所以我们有:

dp[fa][0]=\sum\max (dp[son][1],dp[son][0]) dp[fa][1]=\sum dp[son][0]

然后考虑唯一性问题：

我们用 1 表示确定，用 0 表示不确定。

考虑根节点不选的情况，如果 dp[son][0]=dp[son][1] ，也就是说这个孩子选和不选是一样的，那么肯定会存在选与不选两种情况，所以肯定是不唯一的。

当孩子的值都不相同时，那么如果我们选那个孩子的状态的唯一性不确定，那么父亲的唯一性就不确定。

考虑根节点选的情况，孩子肯定都不选，如果说存在 f[son][0]=0 时，那么父亲点的唯一性就不确定。

tips

我们会发现转移到根节点之后还要判断很多种情况，例如 dp[root][0] 和 dp[root][1] 的大小这类问题。

还有一些树形 dp 问题在画图之后是一个森林，根节点不唯一。

这时候我们可以建一个虚根，让它与所有没有父亲的节点相连，将森林转化成一课树，直接求得虚跟节点的值即可。

最后提醒一句，多组数据千万不要忘记清数组。

code

/*
    树形dp(最大独立集+唯一性判定)
    date:2022.8.1
    worked by respect_lowsmile 
*/
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
using namespace std;
const int N=505;
struct node
{
    int to,next;
};
vector<int> E[N];
int dp[N][2],f[N][2];
int n,cnt,num;
string s,s1,s2;
map<string,int> mapp;
void dfs(int now)
{
    dp[now][1]=1;
    for(int i=0;i<E[now].size();i++)
    {
        int v=E[now][i];
        dfs(v);
        if(dp[v][0]==dp[v][1])  f[now][0]=0,dp[now][0]+=dp[v][0];
        else if(dp[v][0]>dp[v][1])
        {
            dp[now][0]+=dp[v][0];
            if(!f[v][0])  f[now][0]=0;
        }
        else
        {
            dp[now][0]+=dp[v][1];
            if(!f[v][1])  f[now][0]=0;
        }
        dp[now][1]+=dp[v][0];
        if(!f[v][0])  f[now][1]=0;
    }
}
int main()
{
    while(1)
    {
        cin>>n;
        if(n==0)  break;
        for(int i=0;i<=n;++i)
            E[i].clear();
        memset(f,1,sizeof(f));
        memset(dp,0,sizeof(dp));
        mapp.clear();
        cnt=0;
        cin>>s;
        mapp[s]=++cnt;
        E[0].push_back(mapp[s]);
        for(int i=1;i<n;++i)
        {
            cin>>s1>>s2;
            if(!mapp[s1])  mapp[s1]=++cnt;
            if(!mapp[s2])  mapp[s2]=++cnt;
            E[mapp[s2]].push_back(mapp[s1]);
        }
        dfs(0);
        printf("%d ",dp[0][0]);
        if(f[0][0])  puts("Yes");
        else puts("No");
    }
    return 0;
}