题解 P1099 【树网的核】

· · 题解

发布一篇时间复杂度为O(n)的题解

\text{Prev 1}：读懂题意

什么树网啊，明明就是普通的无根树么……
一直到偏心距（\text{E CCF}（为什么去不掉这个空格？））以前相信大家都能看懂……
然后题目要求直径上的一段路径，使其在长度\leq s的前提下偏心距最小。
把题目从\text{CCF}语言翻译成现代汉语，就是：

给定一棵带边权无根树，在其直径上求出一段长度不超过s的路径F，使得离路径距离最远的点到路径的距离最短。

\text{Prev 2}：直径的定义与性质及其引发的思考

首先，明白一件事：对于直径上任意一个点，到它本身的距离最远的点一定是直径的某个端点。理由很简单：如果存在某个点P使得直径上的点A到其的距离超过点A到直径的两端距离的最大值，那么我们可以将直径的一个端点与A分离开，并且接上AP得到一条比直径更长的路径。但是根据定义，直径应该是整棵树上的最长路径，因此，之前的那条直径是一条假的直径。换句话说，假设不成立。
然后考虑对于直径上的一条路径F，有哪些因素会对其偏心距造成影响。
为了方便描述，

using 直径::路径;

首先，肯定会有路径两端点分别到直径两端点对答案造成影响。并且设路径端点、直径端点分别为A_1,A_2,P_1,P_2，如果对答案造成影响的是A_1,P_1或者A_2,P_2，那么A_1P_1路径F的交点只有A_1，A_2P_2与路径F的交点只有A_2。
那么，路径F的长度越长答案一定越优吗？
显然不是这样的。
因为刚刚只考虑了A_1,A_2对答案的贡献。但是路径上的其它点对答案其实也有贡献。比如说对于下面的这幅图：

当s=18时答案应该为3，但是如果只考虑A_1,A_2的贡献，计算结果则会变成0。
从上图不难看出，路径上其它点Q对答案的贡献为：不经过路径上任何其它点所能到达的最远点的距离。不难发现实际计算答案时即使把路径端点的这种“贡献”计入总贡献也不会产生影响（因为端点的第一种贡献更大，“掩盖住了”这种贡献）。
那么如果一棵树有多条直径怎么办呢？没关系，任选一条即可。首先，两条直径不可能不相交。把相交的那一部分看成一个点，剩下的直径部分就会关于这个点对称。而如果选择的路径包含了分叉点，其偏心距就是恒定的（这个分叉点到直径末端的距离），所以可以任选一条直径求解。

\text{Main}：解题过程

本题可以使用邻接矩阵存图，但是为了修改方便，也为了降低空间间复杂度（\text{BZOJ}上这道题的数据规模被增强到了n \leq 5 \times 10^5）此处仍然使用邻接表存图。 

struct Point { //点
    int dist = 0, head = 0;
    int fa = 0, fa_dist = 0; //以直径一个端点为根，父节点编号及到其距离
    int cur_dist = 0; //后面用来降低时间复杂度
    bool vis = false;
} pt[305];
struct Path { //边
    int end = 0, weight = 0;
    int next = 0;

    Path(int __end = 0, int __cost = 0, int __next = 0) :
        end(__end), weight(__cost), next(__next) {}
} ph[605];
void set_path(int u, int v, int w) {
    ph[++ptr] = Path(v, w, pt[u].head), pt[u].head = ptr;
    ph[++ptr] = Path(u, w, pt[v].head), pt[v].head = ptr;
}//这个连边函数的写法来自panda_2134大爷

接下来是两次\text{DFS}求出直径。 

void dfs1(int p) { //p表示正在访问哪个点
    if(pt[p].vis) return;
    pt[p].vis = true; //做好标记
    for(int i = pt[p].head; i; i = ph[i].next) {
        int s = ph[i].end;
        if(pt[s].vis) continue;
        pt[s].fa = p,
        pt[s].fa_dist = ph[i].weight,
        pt[s].dist = pt[p].dist + ph[i].weight;
        dfs1(s); //注意要在访问子节点前维护好子节点信息！
    }
}

（这是主函数中对应部分） 

dfs1(1);
int rt, tempx = 0; //tempx保存已经找到的最远点
for(int i = 1; i <= n; ++i) {
    pt[i].vis = false;
    if(pt[i].dist > pt[tempx].dist)
        tempx = i;
}
rt = tempx, tempx = 0;
for(int i = 1; i <= n; ++i)
    pt[i].dist = pt[i].fa =
    pt[i].fa_dist = 0;

dfs1(rt);
for(int i = 1; i <= n; ++i) {
    pt[i].vis = false;
    if(pt[i].dist > pt[tempx].dist)
        tempx = i;
}
int dist1 = 0, dist2 = 0, tot;
while(pt[tempx].fa) //将直径按照从叶子到根的顺序打印到数组del中
    dist2 += pt[tempx].fa_dist,
    del[++m] = tempx,
    pt[tempx].vis = true,
    tempx = pt[tempx].fa;
pt[rt].vis = true, del[++m] = tempx;
tot = dist2;

然后预处理出每个点以第二种方式产生的贡献值（通过一次DFS，主函数中的调用过程比较简单，留给读者自己思考） 

int dfs2(int p) {
    pt[p].vis = true;
    int temp = 0;
    for(int i = pt[p].head; i; i = ph[i].next) {
        int s = ph[i].end;
        if(pt[s].vis) continue;
        pt[s].dist = pt[p].dist + ph[i].weight;
        dfs2(s);
        temp = std::max(temp, pt[s].dist);
    }
    return temp;
}

显然，上面的所有过程都是O(n)的。那么为什么会有其它的O(n^2)的写法呢？
（个人认为本题的主要时间复杂度来自以下过程：）
接着是枚举所选路径的两个端点并且计算答案。这个过程的时间复杂道是O(n^2)，所以，算法总时间复杂度为O(n^2)。对于官方数据n \leq 300轻松通过。

完结撒花？

可是最后面一部分代码呢？不存在的！本题解是O(n)的题解，怎么可能有O(n^2)的代码？
仔细看一下写出的O(n^2)的代码（没写完的请自觉写完）。这不就是一个线性的动态规划嘛！
把记录下来的直径序列看成区间，本题变成了求一个长度不超过s的区间，使得其中所有元素的贡献值的最大值最小。
这种动态规划想到什么？没错，单调队列！
用单调队列维护一下区间元素的第二种贡献值，第一种贡献可以在左/右端点移动的同时计算。具体写法见以下代码。 

std::deque<int> q; //需要#include <deque>（<queue>行）
int ans = 2147483647; //正无穷
for(int i = 1, j = 1; i <= m; dist2 -= pt[del[i]].fa_dist, ++i) {
//dist1是到起始端点的距离，初始化为0
//dist2是到终止端点的距离，初始化为直径长度
    pt[del[i]].cur_dist = dist2; //cur_dist成员表示这个点离终点的距离（没写好，dist最后用来保存第二种贡献值了）
    while(!q.empty() && pt[q.front()].cur_dist - s > pt[del[i]].cur_dist)
        q.pop_front();
    while(j < i && tot - dist1 - dist2 > s)
        dist1 += pt[del[j++]].fa_dist;
    while(!q.empty() && pt[q.back()].dist < pt[del[i]].dist)
        q.pop_back();
    q.push_back(del[i]);
    int temp = std::max(dist1, dist2);
    temp = std::max(temp, pt[q.front()].dist);
    ans = std::min(temp, ans); //状态转移
}

\text{End}：总结

1、我是真的没看出来那个“中心”的概念有什么用……
2、即使原始的数据范围很水，也要尽力优化。AC不是我们的终极目标，我们的终极目标是获得经验。

以上就是我要说的全部内容。由于水平所限，如果大家有什么不满意的地方或是什么建议想要提出，欢迎随时私信我！