题解：P1099 [NOIP 2007 提高组] 树网的核

Firsry · 2025-03-26 17:39:18 · 题解

题解 P1099 【树网的核】

一、题意

设 T=(V,E,W) 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 T 为树网（treenetwork）。

1. 其实是一个无根树，从哪里开始找树的直径都可以。
2. 保证边权为正整数，这个极其关键，在后面的推论中有用到。
3. 关于 (V,E,W) 其实并不重要，只是为了严谨性。

路径：树网中任何两结点 a，b 都存在唯一的一条简单路径，用 d(a, b) 表示以 a, b 为端点的路径的长度，它是该路径上各边长度之和。我们称 d(a, b) 为 a, b 两结点间的距离。D(v, P)=\min\{d(v, u)\}, u 为路径 P 上的结点。

1. 存在唯一简单路径，也就是说一棵树非常标准，不会有重边。而只有一条路，方便了求最后的偏心距。
2. 对于 d(a,b) 比较简单，在后面其他的定义中看得懂就行了。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 T，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

1. 这句话也就是树的直径的定义（他不会希望不知道算法的 OIer 能够现场推出树的直径的算法吧？）。
2. 那个证明挺有意思，在求出树网的核的时候有用。

偏心距 \mathrm{ECC}(F)：树网 T 中距路径 F 最远的结点到路径 F 的距离，即

\mathrm{ECC}(F)=\max\{D(v, F),v \in V\}

对于给定的树网 T=(V, E, W) 和非负整数 s，求一个路径 F，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 s（可以等于 s），使偏心距 \mathrm{ECC}(F) 最小。我们称这个路径为树网 T=(V, E, W) 的核（Core）。必要时，F 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

1. 树网的核首先是一段路径，他有他的长度，也有它包含的节点。
2. 这段路径在树网的直径上，长度小于等于要求的长度 s。把他的节点看成一个集合，然后看树上其他的节点到这段路的最短距离的最大值。树的直径的不同子路可能会有不同的 \mathrm{ECC}，而 core 就是在不同的路径中让 \mathrm{ECC} 最小的那么 一条 / 多条 / 某个节点。
3. 最小偏心距唯一可以保证唯一，因为如果不唯一，更小的那一个所在路径就是核，而其他的就不是。

二、推论

stO StudyingFather %%%%

这部分题解主要是针对 StudyingFather 题解当中 分析 部分的 定理引理证明 的更加通俗化的描述，也会有不同的证明方法，建议也去他的题解中看看数学语言描述的证明。 如果有看不懂或者发现证明不严谨的，欢迎在评论区发言，本蒟蒻会及时更正。

为了简洁以及易懂，以下证明过程中用的是简化的树，只画出了关键的路径以及节点。 下文中 AB 的形式代表 A 到 B 之间的路径的长度，类似于线段的表示方式。图片中也有比较简洁的证明过程，可以考虑优先看图。 大部分的证明都是通过反证法，而反证的一个重点就是推出原本设定的直径在该情况下并不是真正的直径，从而推出矛盾。推荐同学们自己推一推。

引理 1：对于一棵所有边权均为正的树，如果其存在多条直径，则树上必存在一点 p，使得所有直径均经过该点（简单来说，所有直径必交于至少一点）。

这个还是很显然的，即使 C_1、C_2 是两条直径各自的中点（当然这个后面我们也会证明处理其不可能），也有在正权树上 C_1 C_2 之间的距离可以保证比所谓 “直径” 更长，也就出现了矛盾，反证法证明成立。

定理 1：对于一棵所有边权均为正的树，如果其存在多条直径，则各直径的中点（不一定恰好是某个节点，可能在某条边的内部）是唯一的。

这个证明建立在 引理 1 的基础上。 首先有两条直径，假设为 A_1B_1 和 A_2B_2，则 A_1B_1 的长度和 A_2B_2 的长度是一致的，否则仅有长度较长的那一条直径。 其次有交点 C，则有在两条直径上找到一条形如 A_1-C-A_2 的路径。如果说中点不重合而交点位置是重合的，则有在两直径交点的两侧长度是不同的。如图所示，蓝笔标注的中点偏向于一侧。 然后通过 C，访问两个比直径一半更长的部分，会得到一个比 A_1B_1 更长的路径，那么直径的假设就被推翻了。

引理 2.1：若两条直径有重叠的部分，则于重叠部分同一端点引出的两条直径的非重叠的部分的长度相等。

这个的证明和 定理 1 的证明非常相似。如果说 C_2B_1>C_2B_2，则有 A_1C_1<A_2C_1，那么就可以找到一条 A_2-C_1-C_2-B_1 比直径 A_1B_1 更长的路径，而这个推翻了直径的假设。

引理 2.2：若路径存在不位于直径上的部分，这条路径对应的偏心距一定不会比全部位于直径上的路径的偏心距的最小值更小。

这一段证明还是写的比较详细的，而从这个定理开始就不是很好证明了。 这里用的不是反证法，而是找到了一个存在。其中只有蓝色的部分是直径，红色部分是一个 ECC 来源的可能。如果说 f_1f_2 并不是直径的一部分，则有 C-f_2-f_1 的路径比 C-B 的路径更短。ECC 来源于直径，那么不在直径上的部分并不会影响结果，所以有 C 点和 st 一整段路径的作用是一致的。

这里是一个经典的错误，也是我最开始只有 70 分的原因：贪心的只去找直径上的距离其实是有问题的。如果说 s>diameter 则有整个直径是一个核，这个时候用贪心的策略 \operatorname{ECC}=0，处理方法在解法部分讲解。

定理 2：设在所有满足长度限制的路径中，取得最小偏心距的路径得到的偏心距为 \operatorname{minECC}，则对于任意一条直径，都存在一条长度不超过 s 的路径 F，使得 \operatorname{ECC}(F)=\operatorname{minECC}。

定理 2 推出之后，可以不用处理多条直径，因为对于任意一条直径都有答案。 首先是这里有多条直径，由 引理 2.2 可以得到答案来源于直径上，而包含直径的重合部分一定会是更好的情况，也就是说没有哪一条直径会有单独的更好的选择，所以只用处理一条直径了。

三、代码

对于贪心策略错误的问题，我们找到每个节点不经过当前找到的直径上节点能够到达的最远的距离。 方法其实就是标记直径上的节点“已访问”，然后通过跑一遍深搜，保存在 dia 数组里面。

这里借鉴的是小蓝书的最优解。其他部分在其他题解中有详细的讲解，这里就不赘述了。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 300 + 5;
struct Edge {
    int to, weight;
    Edge(int to = 0, int weight = 0) {
        this->to = to;
        this->weight = weight;
    }
};
int n, s;
vector<Edge> e[MAXN];

int c;
int dep[MAXN], f[MAXN];

int cnt;
int dia[MAXN], pres[MAXN], posts[MAXN];
bool vis[MAXN];

void in() {
    int from, to, weight;
    scanf("%d%d", &n, &s);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &from, &to, &weight);
        e[from].emplace_back(to, weight);
        e[to].emplace_back(from, weight);
    }
    return;
}
void dfs(int from, int fa) {
    f[from] = fa;
    for (auto edge : e[from]) {
        if (edge.to == fa || vis[edge.to])
            continue;
        dep[edge.to] = dep[from] + edge.weight;
        if (dep[edge.to] > dep[c]) 
            c = edge.to;
        dfs(edge.to, from);
    }
    return;
}
void get_diameter() {
    dfs(1, 0);
    dep[c] = 0;
    dfs(c, 0);
    for (int from = c; from; from = f[from]) {
        cnt++;
        dia[cnt] = from;
        pres[cnt] = dep[from];
    }
    reverse(dia + 1, dia + cnt + 1);
    reverse(pres + 1, pres + cnt + 1);
    for (int i = cnt; i > 0; i--)
        posts[i] = pres[cnt] - pres[i];
    return;
}
void solve() {
    for (int i = 1; i <= cnt; i++)
        vis[dia[i]] = true;
    int maxD = 0;
    for (int i = 1; i <= cnt; i++) {
        dep[dia[i]] = 0, c = 0;
        dfs(dia[i], 0);
        maxD = max(dep[c], maxD);
    }
    int minECC = 1 << 30;
    for (int l = 1, r = 1; l <= cnt; l++) {
        while (r <= cnt && pres[r + 1] - pres[l] <= s)
            r++;
        minECC = min(max(maxD, max(pres[l], posts[r])), minECC);
    }
    cout << minECC;
    return;
}

int main() {
    in();
    get_diameter();
    solve();
    return 0;
}