Luogu P4178 Tree

Luogu P4178 Tree

难度：省选/NOI-
标签：点分治
\(\mathtt{blog}\)

\(n\) 个点的树，边 \((u_i，v_i)\) 有边权 \(w_i\)，询问距离 \(\le k\) 的点对数量。

数据范围：\(n\le 4\times10^4,1\le w_i\le10^3,1\le k_i\le 2\times10^4\)。

这里只讲 Calc 操作的实现方法：

发现经过根节点的路径都具有一个性质 \(Dis_{u,v}=Dis_{u,G}+Dis_{G,v}(top_u\not=top_v)\)，\(G\) 为根节点，\(top_x\) 为 \(x\) 结点在子树中除根节点最靠上的祖先。便可以遍历一遍子树求出 \(Dis_{x,G}\) 和 \(top_x\)。
对于 \(\le k\)，选择对 \(Dis\) 排序，用 \(l,r\) 指针维护当下界是 \(Dis_{l,G}\) 时 \(Dis_{G,r}\) 中 \(r\) 的上界，若 \(Dis_{G,l}+Dis{G,r}>k_i\)，则 \(r\gets r-1\)；同理，若 \(\le k\)，则答案就会加上 \(r-l-cnt_{top_l,l+1\sim r}\)，然后 \(l\gets l+1\)，\(cnt_{c,x\sim y}\) 为 \(i=[x,y]\) 中 \(top_i=c\) 的数量，因为要去掉在同一个子树内的结点数量，\(cnt\) 数组维护不阐述，实现见 \(\mathtt{Code}\)。

因为带有排序多一个 \(\log\) 时间复杂度 \(O(n\log^2n)\)。

\(\mathtt{Code}\)