思路:树上dp
考虑对于母星1号点,如果他有至少两个子树,两艘探测船必然分别进入不同的子树(否则除母星外会经过公共星球)。我们规划一艘船进入其中一棵子树,另一艘船进入另一棵子树。
这里假设一艘船进入A子树,另一艘船进入B子树。对于A子树中的那艘船来说,它的路径就是从母星出发沿A子树的航道走一条简单路径,所以我们的任务是找一条从母星到A子树中叶子的最大权值和。对于B子树中的那艘船来说,它也可以在其子树内继续探索,问题同样可以递归地求解。
学过递归的人应该会有感觉,这种大问题化成小问题的结构可以用递归,然后我们可以记忆化它,也就是动态规划的思路。
由于对于每颗子树可能都有两种情况(例如上面提到的A,B子树),所以定义: dp[i][0] 代表从i出发,走一条简单路径所能获得的最大能量值