本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-14 19:54:59

暴力子树加最差复杂度是方的，因为每个点会被加入许多次。准确的说，会暴力加其深度加一次，因为其到根的链上每个点的答案都由它贡献。

发现 DFS 整体是有一条回溯链的。这条链上的点是不需要重复加入与删除的。取这条链为重链，那么有对任意点，其到根的轻边是 $\log$ 级的，整体复杂度是 $O(n\log n)$ 的。