UOJ Logo

NOI.AC

1S 512MB

#241. distance

Statistics

【题目描述】

给一颗 n 个点的无根树,每条边都有一个边权,有两个关键点,所有点到关键点的距离定义为到这两个关键点距离的较小值。现有 q 次询问,每次询问给你两个关键点,求所有点到关键点距离的最大值。

【输入格式】

第一行两个整数 n,q, 分别表示点数和询问数。接下来 n − 1 行,每行三个正整数,u,v,w, 表示 u 和 v 之间有一条边权为 w 的无向边。接下来 q 行,每行两个正整数 u,v, 表示两个关键点。

【输出格式】

对于每个询问,输出所有点到关键点距离的最大值。

【样例 1 输入】

4 3
1 4 1
1 2 1
2 3 1
1 4
1 3
2 3

【样例 1 输出】

2
1
2

【数据范围】

对于 100% 的数据,$n,q ≤ 1000, w ≤ 1 ∗ 10^9$