| Id | 1870 |
| Title | Rebuilding Roads |
| Tags | dp trees |
| Brief solution | dp[i][j]表示i的子结点中，和i连通的结点数为j的时候，需要在i的子树中砍去的最少边数。枚举i的子树，然后O(n^2)完成背包dp，完成dp[i]的更新（注意子树贡献为0的时候的值）。要注意一个细节：我们是在已有size(i)个结点的子树上进行砍边操作，而不是已知i这个结点，然后在上边连一些子树。所以为了dp方便，我们可以用另外一种状态表示：用dp[i][j]表示在i的子树中，去掉j个结点剩下的全部结点和i连通时的最优解（两种状态表示本质上一样）。最后dp[ROOT][p]和dp[NON-ROOT][p]+1中找出最优解。 |