P4886 快递员

    • 65通过
    • 1.3K提交
  • 题目提供者 暴力铠之巨人
  • 评测方式 云端评测
  • 标签 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Bob 的城市里有 $n$ 个邮递站,由于经济考虑,这些邮递站被 $n - 1$ 条带权无向边相连。即:这 $n$ 个邮递站构成了一棵树。

    Bob 正在应聘一个快递员的工作,他需要送 $m$ 个商品,第 $i$ 个商品需要从 $u$ 送到 $v$。由于 Bob 不能带着商品走太长的路,所以对于一次送货,他需要先从快递中心到 $u$,再从 $u$ 回到快递中心,再从快递中心到 $v$,最后从 $v$ 返回快递中心。换句话说,如果设快递中心是 $c$ 号点,那么他的路径是 $c \rightarrow u \rightarrow c \rightarrow v \rightarrow c$。

    现在 Bob 希望确定一个点作为快递中心,使得他送货所需的最长距离最小。显然,这个最长距离是个偶数,你只需要输出最长距离除以 $2$ 的结果即可。

    输入输出格式

    输入格式:

    第一行输入两个数 $n, m$,意义如上。

    接下来$n-1$行,每行三个数 $u_i, v_i, w_i$,表示一条连接 $u_i, v_i$,长度为 $w_i$ 的边。

    接下来 $m$ 行,每行两个整数 $u_i, v_i$,表示商品的起止位置。

    输出格式:

    一行一个整数,表示答案。

    输入输出样例

    输入样例#1: 复制
    3 1
    1 2 1
    2 3 1
    1 3
    
    输出样例#1: 复制
    2

    说明

    对于 $25\%$ 的数据,满足 $1 \leq n, m \leq 1000$。

    对于 $100\%$ 的数据,满足 $1 \leq n, m \leq 10^5, 1 \leq w_i \leq 1000$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。