P6670题解
_wkjzyc
·
·
题解
题意是在有边权的树上寻找平均边权与 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。
$$\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交了两页半……~~
核心代码：
```cpp
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)$。