ABC298Ex(2)

多次询问 \(L,R\)，求 \(\sum\limits_{i}\min(d(i,L),d(i,R))\)。

不失一般性的令 \(dep_L\ge dep_R\)。

考虑 \(i\) 到 \(L/R\) 的路径是怎样的。一定是 \(i\) 到 \(L\rightarrow\) 上的某一点 \(x\) 再到 \(L/R\)。

如果按照每个点到达 \(L/R\) 对其进行染色，则每种颜色都只有一个联通块，换句话说，颜色是树的一个划分。

考虑 \(L\rightarrow R\) 路径上的染色情况，一定有一个阈值 \(m\)，满足路径上到 \(L\) 距离不超过 \(m\) 的点到达 \(L\)，其余到达 \(R\)。利用倍增求出 \(L\) 的树上 \(m\) 级祖先 \(x\)，设 \(\operatorname{lca}(L,R)=k\)，则 \(x\) 必然位于 \(L\rightarrow k\) 的路径上（保证了 \(dep_L\ge dep_R\)）。不难发现所有位于 \(x\) 子树内的点都会走到 \(L\)，其余都会走到 \(R\)。

因此答案就是 \(\sum\limits_{i\in\text{subtree}_x}d(i,L)+\sum\limits_{i\notin\text{subtree}_x}d(i,R)\)。

\(i\notin\text{subtree}_x\) 并不好处理，将答案改写为 \(\sum\limits_{i\in\text{subtree}_x}d(i,L)+\sum\limits_{i}d(i,R)-\sum\limits_{i\in\text{subtree}_x}d(i,R)\)。

此时式子已经相较于一开始变得更好处理，只需要求出一棵子树的所有点到子树内某点的距离和即可。即 \(\sum\limits_{i\in\text{subtree}_x}d(1,i)+d(1,p)-d(1,\operatorname{lca}(i,p))\)。

\(\sum\limits_{i\in\text{subtree}_x}d(1,i)+d(1,p)\) 是好求的，考虑怎么求 \(\sum\limits_{i\in\text{subtree}_x}d(1,\operatorname{lca}(i,p))\)。

对 \(\operatorname{lca}(i,p)\) 拆贡献。设 \(p\rightarrow x\) 经过的点为 \(\{\alpha_z\}\)。则为 \(\sum\limits_{1\le j\le z}d(1,\alpha_j)\times(s_{\alpha_j}-s_{\alpha_{j-1}})\)。

其中 \(s_i\) 代表 \(i\) 的子树大小，\(s_{\alpha_0}=0\)。