换根 DP

一句话理解

换根 DP：一次 DFS 得到以每个点为根的答案。

为什么要学

避免 n 次树 DP。

讲解

先以 1 为根算出 down，再第二次 DFS 用父信息推 up。

例子

到根距离和、每个点当根的子树统计。

常见错误

• 第二次把父亲信息重复加儿子。要减掉当前儿子再加。
• 有环。