题解UVa1220 Hali-Bula的晚会

刘汝佳大法好！

是不是感觉看到这题很熟悉？好像很像没有上司的舞会这题诶！

可是我们发现，这里还新加了一个“判断唯一性”的任务。

我们定义：

$d(u,0)$表示不选$u$的$u$的子树的最大独立集的节点个数

$d(u,1)$表示选$u$的$u$的子树的最大独立集的节点个数

$f(u,0)$表示不选$u$的$u$的子树的最大独立集的唯一性（$0$不唯一，$1$唯一）

$f(u,1)$表示选$u$的$u$的子树的最大独立集的唯一性（$0$不唯一，$1$唯一）

则

$$d(u,1)=1+\sum_{(u,v)\in E}d(v,0)$$

$$d(u,0)=\sum_{(u,v)\in E}\max\{d(v,0),d(v,1)\}$$

以上两个就是求最大独立集的转移方程。

然后考虑怎么判断唯一性。

对于$f(u,1)$的情况：如果$u$的任意一个儿子$v$的$f(v,0)=0$，那么$f(u,1)$就等于$0$。

对于$f(u,0)$的情况：设$v$为$u$的任意一个儿子

• 若$d(v,0)=d(v,1)$，则$f(u,0)=0$。
• 若$d(v,0)>d(v,1)$且$f(v,0)=0$，则$f(u,0)=0$。
• 反之亦然。

以下为代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=205;
int n,tot=0,target[N],pre[N],last[N];
int d[N][2],f[N][2];
map<string,int> mp;
void add(int u,int v) {
    target[++tot]=v;
    pre[tot]=last[u];
    last[u]=tot;
}
void dfs(int u) {
    if(!last[u]) {
        d[u][0]=0;f[u][0]=1;
        d[u][1]=f[u][1]=1;
        return ;
    }
    f[u][1]=1;f[u][0]=1;
    d[u][0]=0;d[u][1]=1;
    for(int ptr=last[u];ptr;ptr=pre[ptr]) {
        dfs(target[ptr]);
        if(f[target[ptr]][0]==0) f[u][1]=0;
        d[u][1]+=d[target[ptr]][0];

        int v=target[ptr];
        if(d[v][0]==d[v][1]) f[u][0]=0,d[u][0]+=d[v][0];
        else if(d[v][0]>d[v][1]) {
            if(!f[v][0])f[u][0]=0;
            d[u][0]+=d[v][0];
        }
        else if(d[v][0]<d[v][1]) {
            if(!f[v][1])f[u][0]=0;
            d[u][0]+=d[v][1];
        }
    }
}
int main(){
    while(cin>>n && n) {
        string x,y;
        mp.clear();
        tot=0;
        memset(last,0,sizeof(last));
        cin>>x;
        int cnt=0;
        mp[x]=++cnt;
        rep(i,1,n-1) {
            cin>>x>>y;
            if(!mp.count(x)) mp[x]=++cnt;
            if(!mp.count(y)) mp[y]=++cnt;
            add(mp[y],mp[x]);
        }
        dfs(1);
        if(d[1][0]==d[1][1]) printf("%d No\n",d[1][0]);
        else if(d[1][0]>d[1][1]) {
            printf("%d ",d[1][0]);
            if(!f[1][0]) printf("No\n");
            else printf("Yes\n");
        }
        else if(d[1][0]<d[1][1]) {
            printf("%d ",d[1][1]);
            if(!f[1][1]) printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}