POJ 2114 Boatherds / Luogu P3806 【模板】点分治1

POJ 2114 Boatherds / Luogu P3806 【模板】点分治1

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

\(n\) 个点的树，边 \((u_i，v_i)\) 有边权 \(w_i\)，\(m\) 次询问，单次询问是否存在两点间的路径长度为 \(k_i\)。

POJ 数据范围：\(n\le10^4,m\le 100,1\le w_i\le 100,1\le k_i\le 10^7\)。
Luogu 数据范围：\(n\le 10^4,m\le100,1\le w_i\le10^4,1\le k_i\le 10^7\)。

点分治纯模板，后面开坑算法浅谈再细讲。

大致思路：

对于这样一颗树（假定根为 \(1\) 结点，根节点应选取该子树的重心，后文会提到）：

把之中的路径分为 \(2\) 部分解决：

1. 经过根 \(1\) 结点的路径。
2. 不经过根 \(1\) 结点的路径。

对于第 2 种，可以继续对其子树进行同样的操作分为 \(2\) 种一直递归到叶子结点为止。

对于第 1 种，发现经过根节点的路径都具有一个性质 \(Dis_{u,v}=Dis_{u,G}+Dis_{G,v}(top_u\not=top_v)\)，\(G\) 为根节点，\(top_x\) 为 \(x\) 结点在子树中除根节点最靠上的祖先。便可以遍历一遍子树求出 \(Dis_{x,G}\) 和 \(top_x\)。这也是根节点选取重心的原因，因为需要遍历整个树，这样最大的一个子树也不会超过 \(\frac{n}{2}\)，\(n\) 为当前数结点个数，最多就只会有 \(\log n\) 层，所以时间复杂度 \(O(n\log n)\) 是点分治打底的。
对于凑出 \(k_i\)，选择对 \(Dis\) 排序，用 \(l,r\) 指针维护两数之和，若 \(Dis_{G,l}+Dis{G,r}>k_i\)，则 \(r\gets r-1\)；同理，若 \(<k_i\)，则 \(l\gets l+1\)；当 \(=k_i\) 时，还需要判断 \(top_l\) 与 \(top_r\) 的关系，如果不等说明可以凑出，若相等需进行进一步讨论决定 \(l,r\) 哪个指针移动。

记录下询问只需要跑一次操作处理完答案即可，时间复杂度 \(O(n\log^2n+mn\log n)\)。

小优化：发现这个树的长度拉满会到 \(n\times \max{w_i}=10^8\)，而要求的答案 \(k\le 10^7\)，若根结点至该结点的长度已经 \(>k\) 则肯定无用不用继续递归。

\(\mathtt{Code}\)