一类树形 dp 方程的可换根化处理

换根 dp 是一个广为流传的算法。
换根 dp 对于 dp 方程是有要求的，一般而言 dp 方程中只能含有常数和与 i 的子树有关的项。
本文将探讨对于下述方程如何使其可以换根处理

$f[p]=(\sum_{e} w_e\times f[son])+\text{dep}_p$

我们假设以 1 为根且 $\text{dep}_1=0$ 。
考虑将贡献归到每个点上，那么当目前枚举到子树 $p$ 时，$p$ 的子树内的点 $x$ 的贡献应该是 $\text{dep}_x\times \prod w$ 。
换根 dp 的方程中不能有 $\text{dep}$ ，故我们将 $\text{dep}_x$ 拆到从 $x$ 到根的每一条边上。并且将每一条边与与其相连的子节点对应。换句话说，当枚举到子树 $p$ 时，我们只计算 $p$ 的子树内除 p 以外的节点的相对深度+1的贡献（如果理解了将边视作相连的子节点上的话，那么 +1 也好理解了）。$p$ 的贡献留在 $p$ 的父节点计算。
带入数值考虑可能形象一点。当枚举到子树 $p$ 时，假设 $x$ 的相对深度为 $a$ ，路径权值之积为 $b$ ，那么当枚举到子树 $\text{fa}_p$ 时，$x$ 的贡献会发生变化： $a\times b\rightarrow (a+1)\times b\times w$ 。

将之后的贡献拆开成 $a\times b\times w+b\times w$ 。前面的 $a\times b$ 恰好是 $x$ 之前的贡献，我们直接设为 f[p]，表示 $p$ 的子树内除 $p$ 以外的节点的相对深度+1的贡献；那么问题就在于后面的 $b\times w$ ，也就是路径权值之积的和。我们单独设 g[p] 表示 $p$ 子树内路径权值之积的和，那么我们可以得到转移方程为

$g[p]=\sum_{e} w_e \times g[son]+1\\ f[p]=\sum_{e} w_e \times (f[son]+g[son])+1=(\sum_{e}w_e\times f[son]) +g[p]$

$+1$ 只是方便 $p$ 在向上传递中累计权值。这里需要一个单位元。
上述方程是可以进行换根处理的。我们成功地转化了问题。

有一个小细节：我们将 $\text{dep}_x$ 拆到了边上，并且将边对应到了相连的其子节点上。由于 $\text{dep}_1=0$ ，故我们最终算出来的 f 值只有在第二层才是准确的（贡献只到了第二层的父边就停止了）；而如果 $\text{dep}_1=1$ ，那么我们最终算出来的 f 值就只有根是准确的。