CF2063E Triangle Tree

· · 题解

CF2063E Triangle Tree

大炮轰蚊子。

前置知识：线段树合并或长链剖分，[NOI2020] 命运 或 [十二省联考 2019] 希望。

考虑三角形两条边 a, b(a \le b)，则第三边 x 需要满足 b - a < x < b + a，于是有 (b + a) - (b - a) - 1 = 2a - 1 个。

设 u 子树内深度为 i 的结点数量为 f _ {u, i}，f _ u 的后缀和为 h _ u，则

f _ {u, i} = [dep _ u = i] + \sum _ {v \in \operatorname {son} (u)} f _ {v, i}

当 LCA 为 u 时对答案的贡献为：

\sum _ {v, w \in \operatorname {son} (u), v \neq w} \sum _ {i = 1} ^ {n} (2i - 2dep _ u - 1) (f _ {v, i} h _ {w, i} + f _ {w, i} h _ {v, i + 1})

可以线段树合并（这里还需要维护一个区间深度和），在合并的过程中统计答案（类似 [PKUWC2018] Minimax），时空复杂度都为 O(n \log n)，代码。

有关深度的信息也可以长链剖分（这里用树状数组维护动态后缀和），在暴力添加短儿子贡献时统计答案，相比线段树合并在空间上少了个 \log n，细节多一车，先不写了。