New Editorial for Problem #14292

这个题可以做到线性。

长剖，维护每个点的答案数组。处理到一个点时直接将重儿子的答案数组拿过来，轻儿子直接暴力加入，根据长剖理论只有 $O(n)$ 次加入。现在难点在于加入根，是区间加等差数列，线段树维护做到 $1\log$。

我们发现可以先别加入当前长链上的点，这样答案依然可以很简单的计算。在链头加入整条链的贡献即可，这样只需要扫一遍答案数组即可处理。时间复杂度 $O(n+m)$。

QOJ.ac