1. 题目描述

公司里有$n, n \in [1, 200]$个人，他们间的关系构成树状结构。除老板外，每个员工都有唯一一个直属上司，要求从中选择尽量多的人，但是不能同时选择员工和他的直属上司，问最多能选多少人，以及可行解是否是唯一的？

2. 基本思路

这显然又是一个树形DP的题目，经典模型——树的最大独立集。《算法竞赛入门经典》中的典型例题，唯一稍微不同的是需要判断可行解是否唯一。因此，先分析状态：

（1） $dp[u][0]$表示不选$u$的最大人数，$f[u][0]$表示当前选择是否唯一，此时可以选择、也可以不选择$u$的下属；

（2） $dp[u][1]$表示选择$u$的最大人数，$f[u][1]$表示当前选择是否唯一，此时一定不能选择$u$的下属；

可以很容易推导状态转移方程：

\begin{align}

    dp[u][0] &= \sum \max (dp[v][0], dp[v][1])  \\

    f[u][0]  &=  \bigwedge \Big( (dp[v][0] \neq dp[v][1]) \wedge f[v][dp[v][0] < dp[v][1]] \Big) \\

    dp[u][1] &= \sum dp[v][0]   \\

    f[u][1]  &= \bigwedge f[v][0]

\end{align}

可以使用刷表法进行实现这个DP，经典的树形DP模型。

3. 代码

1 /* uva1220 */  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include