[NOI2003] 逃学的小孩 / 数据生成器

GitHub跳转原题关系图返回列表

树的直径加任意点到两个直径端点的较小距离，得到最坏寻找时间。

OJ: luogu

题目 ID: P4408

难度:普及+/提高-

标签:树的直径最短路树python

日期: 2026-07-17 02:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

父母先去离 Chris 家较近的两个朋友之一，再去另一个，求所有位置的最坏总路程。

思路

固定树直径端点 A,B。对 Chris 位置 C，最坏路线长度为 dist(A,B)+min(dist(C,A),dist(C,B))；取所有 C 的最大值即可。三次树遍历得到两端距离数组。

Python 知识

  • map(min, zip(from_a, from_b)) 同时逐点取两个距离的较小值。
  • 带权树仍可用列表遍历，因为树中没有重复访问的边。
  • max(..., key=distance.__getitem__) 是找最远端点的常用模式。

代码

python
import sys


input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(edges):
    u, v, weight = map(int, input().split())
    graph[u].append((v, weight))
    graph[v].append((u, weight))


def distances(start):
    distance = [-1] * (n + 1)
    distance[start] = 0
    order = [start]
    for node in order:
        for neighbor, weight in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + weight
                order.append(neighbor)
    return distance


from_one = distances(1)
first = max(range(1, n + 1), key=from_one.__getitem__)
from_first = distances(first)
second = max(range(1, n + 1), key=from_first.__getitem__)
from_second = distances(second)
print(from_first[second] + max(map(min, zip(from_first[1:], from_second[1:]))))

原有 C++ 版本仍保留：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:04
 * update_at: 2026-07-17 01:04
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

时间 O(n)，空间 O(n)。

总结

把“先近后远”的路线长度拆成直径和一个端点较小距离，最坏情况就能由直径刻画。