$Grass$Grass $Planting$Planting 题解

题目

解题方法

方法 $1$1：树形 $dp$dp

设 $dp_i$dpi​表示以 $i$i为根的子树需要使用的最少的草的种类数， $f_i$fi​表示 $i$i节点的儿子个数， $b_i$bi​表示与 $i$i结点相连的结点数量。
除了根节点以外的其他结点都与 $b_i$bi​个结点相连，而有一个结点恰好是它的父亲结点。但是由于根结点没有父亲结点，因此
$f_i=\begin{cases} b_i-1&i>1\\ b_i&i=1 \end{cases}$fi​={bi​−1bi​​i>1i=1​
注：这里我们假定 $1$1是整棵树的根。
那么可以得到
$dp_i=\max_{j\in son_i}{(dp_j,f_i+1,f_j+2)}$dpi​=maxj∈soni​​(dpj​,fi​+1,fj​+2)
注： $son_i$soni​表示 $i$i的儿子。
上面式子的 $dp_j$dpj​表示以 $j$j为根的子树需要使用的最少的草的种类数， $f_i+1$fi​+1表示 $i$i的儿子的数量再加上 $i$i这个结点， $f_j+2$fj​+2表示 $j$j的儿子的数量再加上 $i$i和 $j$j两个结点。
那么答案就是 $dp_1$dp1​。
时间复杂度为 $O(n)$O(n)。

方法 $2$2：数学

设 $b_i$bi​表示与 $i$i结点相连的结点数量。
我们可以发现，答案就是 $\max_{i=1}^{n}{b_i}+1$maxi=1n​bi​+1。
时间复杂度为 $O(n)$O(n)。