课堂总结

由 n 个点，n - 1 条边组成的连通图为树，树上两个点有且只有一条路径。如果指定任意一个点为根，以根出发遍历整个树就会形成 parent-child 关系，除了根以外每个点只有一个 parent，没有孩子的点称为叶子结点。 每个点往下遍历形成一颗子树，dfs 做题时有时需要维护子树的答案. Potion Farming 这道题就需要维护子树叶子的数量以及能获取的药水总数. 每个子树能够获取的药水总数显然不大于其叶子数量，需要在 dfs 回溯过程中处理答案.