「NOI2003」逃学的小孩

#题面

#题目描述

Chris 家的电话铃响起了，里面传出了 Chris 的老师焦急的声音：“喂，是 Chris 的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris 的父母就心急如焚，他们决定在尽量短的时间内找到 Chris。他们告诉 Chris 的老师：“根据以往的经验，Chris 现在必然躲在朋友 Shermie 或 Yashiro 家里偷玩《拳皇》游戏。现在，我们就从家出发去找 Chris，一旦找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris 居住的城市由 $N$ 个居住点和若干条连接居住点的双向街道组成，经过街道 $x$ 需花费 $T_{x}$ 分钟。可以保证，任意两个居住点间有且仅有一条通路。Chris 家在点 $C$，Shermie 和 Yashiro 分别住在点 $A$ 和点 $B$。Chris 的老师和 Chris 的父母都有城市地图，但 Chris 的父母知道点 $A$、$B$、$C$ 的具体位置而 Chris 的老师不知。

为了尽快找到 Chris，Chris 的父母会遵守以下两条规则：

1. 如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，那么 Chris 的父母先去 Shermie 家寻找 Chris，如果找不到，Chris 的父母再去 Yashiro 家；反之亦然。
2. Chris 的父母总沿着两点间唯一的通路行走。

显然，Chris 的老师知道 Chris 的父母在寻找 Chris 的过程中会遵守以上两条规则，但由于他并不知道 $A$、$B$、$C$ 的具体位置，所以现在他希望你告诉他，最坏情况下 Chris 的父母要耗费多长时间才能找到 Chris？

#输入格式

输入文件第一行是两个整数 $N$ 和 $M$，分别表示居住点总数和街道总数。

以下 $M$ 行，每行给出一条街道的信息。第 $i+1$ 行包含整数 $U_{i}$、$V_{i}$、$T_{i}$，表示街道 $i$ 连接居住点 $U_{i}$ 和 $V_{i}$，并且经过街道 $i$ 需花费 $T_{i}$ 分钟。街道信息不会重复给出。

#输出格式

输出文件仅包含整数 $T$，即最坏情况下 Chris 的父母需要花费 $T$ 分钟才能找到 Chris。

#输入输出样例

样例输入 #1

4 3
1 2 1
2 3 1
3 4 1

样例输出 #1

4

#数据范围与约定

对于 $100\%$ 的数据，$3 \le N \le 2\times 10^5$，$1 \le U_{i},V_{i} \le N$，$1 \le T_{i} \le 10^{9}$。

#思路

据说这题还有另一版题面，叫「数据生成器」。

首先，题目中保证了任意两个居住点间有且仅有一条通路，所以这个图是一棵树，那么这道题就是一个树上问题了。

其次，由题意可以得出 $A$、$B$、$C$ 三点不会重合。

那么显然有 $A$、$B$ 一定在树的直径的两端，因为只有在这两个位置才能保证选择的 $C$ 点到 $A$ 点的距离和到 $B$ 点之间的距离的最小值最大。

那么确定了 $A$ 点和 $B$ 点的位置以后，再求出 $A$、$B$ 两点分别到各点的最短距离，然后枚举 $C$ 点的位置即可。

最后的答案就是 $\mathrm{dis}(a, b) + \max{\{\min{\{\mathrm{dis}(a, c), \mathrm{dis}(b, c)\}}\}}$。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m;
long long ans;
std::vector<std::pair<int, long long>> g[N];
long long dep1[N]{-1}, dep2[N]{-1};

void dfs(int u, int f, int w, long long *dep) {
    dep[u] = dep[f] + w;

    for (auto [v, w] : g[u]) {
        if (v == f) continue;

        dfs(v, u, w, dep);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;

        cin >> u >> v >> w;

        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    dfs(1, 0, 1, dep1);

    int a = std::max_element(dep1 + 1, dep1 + n + 1) - dep1;

    dfs(a, 0, 1, dep1);

    int b = std::max_element(dep1 + 1, dep1 + n + 1) - dep1;

    dfs(b, 0, 1, dep2);

    for (int i = 1; i <= n; i++) {
        if (i == a || i == b) continue;

        ans = std::max(ans, std::min(dep1[i], dep2[i]) + dep1[b]);
    }

    cout << ans << endl;

    return 0;
}