题解 UVA1220 【Hali-Bula的晚会 Party at Hali-Bula】
Azazеl
·
·
题解
题目
题意
------------
#### 题解
$\ \ \ \ \ $首先对于选择最多的节点,建议先完成这道题[$P1352$没有上司的舞会](https://www.luogu.com.cn/problem/P1352)
$\ \ \ \ \ $明显看出这题是一道树形$DP$,对于树形$DP$,常见的套路是:**二维:第一维当前是哪一个节点**
$\ \ \ \ \ $对于这道题，每一个节点的状态是**选**或**不选**,所以我们这样定义:
$$\texttt{DP[i][j]:对于i号节点选/不选的最大节点数}$$
$$\texttt{(其中j用来存储选(1)或者不选(0))}$$
$\ \ \ \ \ $那么状态转移方程就很显然了:
* 选择一个点:不能选择其子节点
* 不选一个点:其子节点可选可不选
$\ \ \ \ \ $所以我们可以得到$(u$表示当前节点，$v$表示$u$所有的子节点$)$:
$$\texttt{DP[u][1]+=DP[v][0]}$$
$$\texttt{DP[u][0]+=max(DP[v][1],DP[v][0])}$$
$\ \ \ \ \ $解决节点数都是班子级别的问题，关键是怎么维护答案是否唯一.
$\ \ \ \ \ $接着上面的讲,我们的答案是$max(DP[root][0],DP[root][1])$对吧,那考虑这样一种情况:我们的$DP[root][0]=DP[root][1]$的时候呢?明显是有两种情况对吧.以此类推,如果一个节点它的两个$DP$值相等，这时它肯定有不止一组的解.
$\ \ \ \ \ $理论上，我们可以在执行完上面找根节点的树形$DP$后,找每一个节点的两个$DP$值是否相等.
$\ \ \ \ \ $还有没有更好的办法呢?
$\ \ \ \ \ $我们效仿$DP$的定义,定义:
$$\texttt{Only[i][j]表示对于i号节点选/不选的唯一性}$$
$$\texttt{(其中j用来存储选(1)或者不选(0))}$$
$\ \ \ \ \ $其实就是上面的$DP$定义,那么我们该怎么转移它?
$\ \ \ \ \ $想想刚开始我们看的对于$root$点的情况枚举,我们至少可以分成两类:
* $\texttt{DP[v][0]=DP[v][1]}$那么此时$\texttt{Only[u][0]=flase}$(注意:这个地方只可能是在这个节点不选的情况下才不具有唯一性,因为选了这个节点必定不会选它的子节点,也就不存在多解了)
* $\texttt{DP[v][0]}≠\texttt{DP[v][1]}$那么我们又可以分成下面这两种情况:
* $\texttt{DP[v][0]>DP[v][1]: Only[u][0]=Only[u][1]=Only[v][0]}
-
\texttt{DP[v][0]<DP[v][1]: Only[u][0]=Only[v][1]}
需要注意的是,当DP[v][0]>DP[v][1]时,我们是可以更新一次更新选和不选的情况为true,但反之却只能更新不选的情况为true,我相信这很好证明 ,所以读者自证.
$$\mathcal{CODE}$$
```cpp
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string a,b,root;
map <string,int> map_;
vector <int> G[205];
int dp[205][5];
bool Only[205][5];
void DP(int u)
{
dp[u][1]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
DP(v);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][1],dp[v][0]);
if(dp[v][1]>dp[v][0]&&Only[v][1]) Only[u][0]=1;
else if(dp[v][0]==dp[v][1]) Only[u][0]=1;
else if(dp[v][1]<dp[v][0]&&Only[v][0]) Only[u][0]=Only[u][1]=1;
}
}
int main() {
int n;
while(scanf("%d",&n)&&n)
{
map_.clear();
for(int i=1;i<=200;i++) G[i].clear();
memset(dp,0,sizeof(dp));
memset(Only,0,sizeof(Only));
int No=1,root;
cin>>a;
root=map_[a]=No++;
for(int i=1;i<n;i++)
{
cin>>a>>b;
if(!map_[a]) map_[a]=No++;
if(!map_[b]) map_[b]=No++;
G[map_[b]].push_back(map_[a]);
}
DP(root);
if(dp[root][0]<dp[root][1])
{
printf("%d ",dp[root][1]);
puts(Only[root][1]?"No":"Yes");
}
else if(dp[root][0]>dp[root][1])
{
printf("%d ",dp[root][0]);
puts(Only[root][0]?"No":"Yes");
}
else
{
printf("%d ",dp[root][0]);
puts("No");
}
}
return 0;
}
```