什么是点覆盖问题？
就是在树上选几个点，覆盖（一个点可以覆盖其相连的边或与其距离不超过 \(d\) 的点，根据题意具体分析）一些点或边，求最小代价。
例题
战略游戏
题意
一棵无根树，一个点可以覆盖与其相连的边，求将整棵树的边覆盖，最少需要放置几个点。
思路
可以发现，根是哪个点，对答案没有影响，那我们就假定1为根，来简化问题。
这样每条边肯定就是连着父亲和儿子，要么被父亲覆盖，要么被儿子覆盖，或者被父亲和儿子一起覆盖。
每个节点都有放和不放两种状态。
设\(dp[i][0/1]\)表示该节点不放和放可以将以i为根的子树的边覆盖的最小代价。
- \(dp[i][0]+=dp[son[i]][1]\)
该点不放，它和它儿子的边就得由儿子来覆盖，儿子必须放。 - \(dp[i][1]+=min(dp[son[i]][0],dp[son[i]][1])\)
该点放，它和它儿子的边已经被该点覆盖，儿子放不放都行，取最小。 - \(ans=min(dp[i][0],dp[i][1])\)
答案来自1号节点放或不放（可以将整棵子树覆盖的最小代价），两者取最小。
时间复杂度：\(O(n)\)
VOCV - Con-Junctions
题意
一棵无根树，一个点可以覆盖与其相连的边，求将整棵树的边覆盖，最少需要放置几个点。并求出最小代价的方案数。
思路
对于第一问，和上一题一样，不再赘述。
来看第二问，求最小代价的方案数。
维护一个 \(g[i][0/1]\)， 表示该节点不放和放可以将以 \(i\) 为根的子树的边覆盖的最小代价的方案数。
在 \(dp\) 值转移时进行维护。\(g\) 的初始值都为1。
- \(dp[i][0]+=dp[son[i]][1]\)，该 \(dp\) 值只能由所有儿子都放转移过来。\(g[i][0]*=g[son[i]][1]\)。
- \(dp[i][1]+=min(dp[son[i]][0],dp[son[i]][1])\)，该 \(dp\) 值有两种转移途径，分三种情况。
- \(dp[son[i]][0]<dp[son[i]][1]\)，\(dp\) 值由 \(dp[son[i]][0]\) 转移过来。
\(g[i][1]*=g[son[i]][0]\) - \(dp[son[i]][0]>dp[son[i]][1]\)，\(dp\) 值由 \(dp[son[i]][1]\) 转移过来。
\(g[i][1]*=g[son[i]][1]\) - \(dp[son[i]][0]==dp[son[i]][1]\)，\(dp\) 值要么由 \(dp[son[i]][0]\) 转移过来，要么由 \(dp[son[i]][1]\) 转移过来，都可以。
\(g[i][1]*=(g[son[i]][0]+g[son[i]][1])\)
- 最后输出第一问：\(min(dp[1][0],dp[1][1])\)。
- 输出第二问：1. \(dp[1][0]<dp[1][1]\)
输出\(g[1][0]\)。
- \(dp[1][0]==dp[1][1]\)
输出 \((g[1][0]+g[1][1])%mod\) 一定要取模啊。 - \(dp[1][0]>dp[1][1]\)
输出\(g[1][1]\)。
时间复杂度：\(O(Tn)\)。