poj 3659 树形dp(树上的最小支配集)
题意:求树的最小支配集。思路:动态规划。一开始每个点只取了两个变量,表示在以其为根的子树中选择和不选择该点的最少点数。由一组数据(6个点的路径)发现了问题,考虑第3个点的时候,如果不选择此点,那么第4个点必须要选取,实际上这是不必的。该组数据的最优解是选择第2和第5个点。那么每个点加上一个变量好了:dp1[x]表示选择第x个点。dp0[x][0]表示不选择第x个点,而且该点并没有被