abc287题解

· · 题解

其他题解做法写的都很详细了，这里主要证明时间复杂度。

先看代码

代码

考虑求每个点被计算了几次，可以发现，只有枚举到其祖先 u 时才会被计算。那么在此时，我们枚举该节点的次数为节点 u 的所有除该节点所在子树的子树大小之和。对于所有的祖先，该节点被枚举次数最坏为 n 次。时间复杂度 O(n^2)。