2020.07.04日常总结

$$\text{UVA1220 Hali-Bula的晚会 Party at Hali-Bula}$$

$\text{[Problem]}$

给你一棵有 $n(1\le n\le 200)$ 个点的树及其树根，每个节点用一个英文字符串表示。你需要从中选择尽可能多的点，使得没有一个点和它的父亲同时被选择。求最多可以选出多少个点。在选出点尽可能多的前提下，输出方案是否唯一。唯一，输出 Yes，不唯一，输出 No。

$\text{[Soluntion]}$

一道树形 $\text{dp}$ 题。

不考虑节点的表示，单单考虑如何求出解先。

DP 一大特色：问什么就求什么。它要你输出些什么，你就把每一项都抽象成一个状态即可。

记 $f_{u,0}$ 表示考虑以 $u$ 为根的子树且 $n$ 不选时最多可以选多少个点，$f_{u,1}$ 类似，表示是 $u$ 选时的方案。类似的，记 $d_{u,0/1}$ 表示是否唯一，下标的含义与 $f$ 完全一致，值为真为唯一，假为不唯一。

$u$ 选，则它的儿子们都必须不选，所以：

$$f_{u,1}=\sum _{v\in \text{son}(u)}{f}_{v,0}$$

故，只有当所有的 $d_{v,0}$ 为真时，$d_{u,1}$ 才为真。

$u$ 不选，其儿子可选可不选，所以：

$$f_{u,0}=\sum _{v\in \text{son}(u)}\max \{f_{v,0},f_{v,1}\}$$

考虑是否唯一：

当 $f_{v,0}=f_{v,1}$ 时，不唯一。

当较大值对应的 $d$ 值为假时，不唯一。

考虑节点的表示，很简单，用个 map 给每个节点一个整数编号即可。

$\text{[code]}$

vector<int> son[210];//儿子 map<string,int> Name;//编号 int f[210][2],n,t;//dp结果 bool unq[210][2];//是否唯一 inline void dp(int u,int fa){ f[u][0]=0;f[u][1]=unq[u][0]=1; unq[u][1]=true;//先初始化数据 int son_number=son[u].size(); for(int i=0;i<son_number;i++){ register int to=son[u][i]; if (to==fa) continue;//重要 dp(to,u);//先递归计算子儿子 if (!unq[to][0]) unq[u][1]=0; f[u][1]+=f[to][0];//u参加舞会 if (f[to][0]>f[to][1]){ f[u][0]+=f[to][0]; if (!unq[to][0]) unq[u][0]=false; } else if (f[to][0]<f[to][1]){ f[u][0]+=f[to][1]; if (!unq[to][1]) unq[u][0]=false; } else{ f[u][0]+=f[to][0]; unq[u][0]=false; } } } int main(){ while (~scanf("%d",&n)&&n){ Name.clear();//清空编号 for(int i=1;i<=n;i++) son[i].clear();//init register string name; cin>>name;Name[name]=t=1; for(int i=2;i<=n;i++){ register string n1,n2; cin>>n1>>n2;//n1与n2有连边 if (!Name[n1]) Name[n1]=++t; if (!Name[n2]) Name[n2]=++t; son[Name[n2]].push_back(Name[n1]); son[Name[n1]].push_back(Name[n2]); } dp(1,0);//递归进行计算 if (f[1][1]>f[1][0]){ printf("%d ",f[1][1]); if (unq[1][1]) puts("Yes"); else printf("No\n"); }//千亿要注意最后的输出 else if (f[1][0]>f[1][1]){ printf("%d ",f[1][0]); if (unq[1][0]) puts("Yes"); else printf("No\n"); } else printf("%d No\n",f[1][1]); } return 0; }