题解 P1099 【树网的核】

天泽龟 · 2019-10-01 00:26:35 · 题解

虽然本题题解已有很多，但基本上是O(N^3)的暴力或O(N)的递推做法，而仍有一种O(N·logN)的做法没人提及，但仍可通过Vijos上N=400000的大数据。

没错，他就是二分。

本文将从二分的正确性，二分的具体实现过程，二分边界等多个方面详细阐述这种解法，希望您在观看过后也能对二分答案有一个更为详细的理解。

顺便，bzoj的加强版挂了，我把数据贴到了洛谷可供给大家验题，戳这。

1. ~二分的正确性/单调性的证明

众所周知，一道题如果能通过二分求解，那么他一定具有单调性。

对于本题而言，如果我们对偏心距进行二分答案，在check函数的变化，那么很显然的是，当你设定的偏心距越大，可满足的核就会越向树的中心集中，s自然也就越小了，所以这是满足单调性的。

然而又由于涉及到边界问题，导致其并非严格单调，关于这个细节部分等到第三节再来细谈。

2.~二分的具体实现过程/check函数

既然我们已经确定了偏心距的范围，那么问题就转化成 “对于一条直径是否存在一个核，长度小于s且偏心距不超过定值mid？”

那我们知道对于树上的任意点，他到其他点的最大距离即为他到某直径端点的距离。从而我们可以推断出，某一核的偏心距实质上也就是 核的端点到直径端点的距离最值。如果我们设直径两端点为A,B，核F的两端点为p,q，那么以上结论就可以表述为：

对于上式，p,q是我们要求的未知范围，而A,B是我们已知的直径端点，易想到去通过A,B去反推p,q。

具体的说，我们可以 以A,B为圆心，以mid为半径画圆 以A,B端点分别向直径内部递推，找到与端点距离不超过mid的最远节点， 此时的两点即为所求的p,q。

最终我们判断p,q两点距离是否小于s，作为我们二分答案的判断标志。注意，这里不用考虑绝对值！！ 如果距离为负，标志着两点范围已经互相越过去到达了对面，那么这时候在范围内随便取一个点都应该是满足的。

对于具体的操作来说，可以先以直径某一端点（如A）为根节点，以此不断向下递归同时记录已走的距离，找到最远满足条件的节点p；对于另一端B可以直接往上不断跳，找到最远满足节点q。

放上check的部分代码：

ll drop(ll u,ll fa,ll x)  //从高往下掉
{
    for (ll i=fir[u];i;i=e[i].nex)
    if (v[e[i].u]) {
        if (e[i].u==fa) continue;
        l1+=e[i].w; if (l1>x) return u;
        else return drop(e[i].u,u,x);
    }
}

ll up(ll u,ll x)  //从低往上爬
{
    while (u!=A&&l2+w[u]<=x) l2+=w[u],u=f[u][0]; 
    return u;
}

bool check(ll x)
{
    l1=l2=0; p=drop(A,0,x); q=up(B,x); 
    return (d[q]-d[p]<=s);
}

算上主函数里的二分，应该是O(N·logN)的时间复杂度。

3.~二分的边界判断

所谓二分边界，就是指放在主程序中的l,r。普遍的来说，二分答案是可以从0取到INTMAX的，但对于本题，情况发生了改变。

我们不妨从一个例子引入：

6 6 
1 2 5 
2 3 3 
3 4 3 
4 5 5 
3 6 6 
错解：5  正解：6

恩？？为什么会这样呢？ 我们来看一下这棵树长什么样：

当我们取{2,3,4}作为核的点集时，按上面的做法，据直径端点的距离应为5，但很显然答案应该是由6号节点造成的6！

相信你肯定恍然大悟了：我们全程没有考虑支链对答案的影响！！

如果放在考场上，相信如果换做我的一位朋友，他一定会心态崩溃，疯狂怀疑二分的正解性，开始胡乱打暴力骗分，最后惨遭爆炸 （你说的这个朋友到底是不是你自己）（这题好像骗分就能AC）。 但是在平常做题，有较多时间的情况下，我们不妨详细探讨一下这个问题。

1. 很明显的是，在众多支链中，仅会有最长支链对答案造成影响（由偏心距的定义可推出）。当核的左右两端点 到直径端点的距离比最长支链到核的距离短的时候，偏心距就不受直径的影响了。

由第一章的证明，在达到边界前仍是满足单调性的，于是我们就大胆猜想：二分边界的上界是树的直径，下界就是最长支链到直径的距离！

我们对其证明：

• 上界应该很好理解，当你假定A这个端点为树的核，那么他的偏心距显然就是树的直径D了。

• 下界我们想要证明的是，会不会出现最长支链到核的距离，小于最长支链到直径距离的情况。

由定义可知，核是直径的一段路径，设最长支链与该直径交于F点，最长支链的叶节点为C，如果F\in \text{核的点集}，那么偏心距必然\geq FC。

如果f\notin \text{核的点集}，那么设核到F的距离为d，由于支链必然小于到直径端点A,B的距离，则亦满足：d+FB\geq d+FC，，取等条件是C是另一直径的端点。上式表明若核不包含F，偏心距仍在直径端点处取得，最长支链无贡献。

形象地说，如果以A为端点找核的话，偏心距应该满足这么一个样子：