题解：CF2063E Triangle Tree

hh弟中弟 · 2025-01-23 14:27:57 · 题解

设 dis_{u,lca}=a,dis_{v,lca}=b，那么这个点对的贡献就是 2\min(a,b)-1。\ 首先上一个启发式合并，树状数组维护单点加，区间查，然后分类讨论这个点是较小还是较大，去树状数组里查就好了。时间复杂度 \mathcal{O}(n\log^2 n)。\ 发现这个还是比较唐，其实可以直接线段树合并，然后合并的时候 \text{pushup} 一下贡献就好了。这样的复杂度是 \mathcal{O}(n\log n)。