题解：CF2063E Triangle Tree

Nt_Tsumiki · 2025-01-23 07:14:07 · 题解

唐诗 DS。

考虑答案到底是个啥，我们令 d_1=\max\{\text{dis}_{u,\text{lca}},\text{dis}_{v,\text{lca}}\},d_2=\min\{\text{dis}_{u,\text{lca}},\text{dis}_{v,\text{lca}}\}，那么答案就是 \sum (d_1+d_2)-(d_1-d_2)-1=\sum 2d_2-1。

考虑咋算，首先后面跟着的 1 是好算的，在 LCA 处统计答案就行，前面的 2d_2=2(\min\{\text{dep}_u,\text{dep}_v\}-\text{dep}_{\text{lca}})，钦定 \text{dep}_v<\text{dep}_u 也就是我们对与每一对合法的 (u,v) 统计 \text{dep}_v-\text{dep}_{\text{lca}}，那我们考虑在 v 处统计答案。

直接按 \text{dep}_u 排序，那对于点 v 总共的 (u,v) 对数是 pos_v-1 对，其中也包含不合法的，但是不合法的在计算时一定被消掉了，因为 \text{LCA}(u,v)=v，直接不管就行，那么 \sum \text{dep}_v 就解决了，然后对于 \sum \text{dep}_{\text{lca}} 直接考虑 P4211 的链加链求和就做完了。

submission