自动搬运

查看原文

来自洛谷，原作者为

	_wkjzyc 曲终人散。

搬运于2025-08-24 22:22:57，当前版本为作者最后更新于2021-02-23 12:08:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意是在有边权的树上寻找平均边权与 $k$ 最接近的链。树上找链的问题可以考虑点分治，而点分治的 $\mathtt{Solve()}$ 函数要处理过重心的链。

记 $dis_x$ 为 $x$ 到重心的边权和， $dep_x$ 为 $x$ 的深度，则链 $(x,y)$ 的平均边权 $P=\frac{dis_x+dis_y}{dep_x+dep_y}$。使其最小则是一个分数规划问题，考虑二分 $\lvert P-k \rvert$。记为 $mid$。

$\mathtt{Check()}$ 函数需判定是否存在 $P$ 至少满足 $k-mid \leq P \leq k$ 与 $k \leq P \leq k +mid$ 其中之一。以前者为例，后者同理。该条件等价于：

$$\begin{cases} (dis_x-dep_x*k)+(dis_y-dep_y*k)\leq 0\\ (dis_x-dep_x*(k-mid))+(dis_y-dep_y*(k-mid))\geq 0\end{cases} $$

令 $f_x=dis_x-dep_x*k$ ， $g_x=dis_x-dep_x*(k-mid)$。 将所有点按照 $f_x$ 排序后尺取法处理：遍历 $x$ 时处理满足第一个条件的 $y$ 范围，再通过维护 $g_y$ 最大值判定范围内是否存在点满足第二个条件。

二分、点分治、排序，时间复杂度 $O(n \log^2 n \log k)$。

还有一些其他细节：

• 点 $x$ 与 $y$ 需位于不同子树，所以维护 $g_y$ 最大值时还要维护一个其他子树中的最大值。

• 链的端点可以在重心上，所以要加入一个 $dis_x=0,dep_x=0$ 的点。

• 输出答案下取整，二分要注意端点的判定。也可以使用实数二分，稍慢但是保险。

• 点分治不要写错！我因为点分治的max打成min交了两页半……

核心代码：

bool CheckAbove(ld mid) {
	ld mn=1e18,dif=1e18,flag; //dif是与最大值子树不同的部分最小值 
	int nmn=-1,ndif=-1; //两个值分别对应的子树编号 
	for(int l=1,r=top+1;l<=top;l++) {
		while(r>1&&f(a[r-1])+f(a[l])>=0) { //处理可行f 
			r--;
			if(h(a[r],mid)<mn&&a[r].num!=nmn) {
				ndif=nmn,nmn=a[r].num,dif=mn,mn=h(a[r],mid);
			} else if(h(a[r],mid)<mn&&a[r].num==nmn) {
				nmn=a[r].num,mn=h(a[r],mid);
			} else if(h(a[r],mid)<dif&&a[r].num!=nmn) {
				ndif=a[r].num,dif=h(a[r],mid);
			} //维护g。由于重名这里用h 
		}
		if(nmn!=a[l].num) flag=h(a[l],mid)+mn; else flag=h(a[l],mid)+dif;
		if(flag<=0) {return 1;}
	}
	return 0;
}

20220414 更新：感谢 @A_Sunny_Day 提醒复杂度为 $O(n \log^2 n \log k)$。