#P18796. [Omi2022] 交通网络
[Omi2022] 交通网络
[Omi2022] 交通网络
题目描述
一座城市的交通网络是一棵有 个顶点的带权树。顶点编号为 到 ,每条边的权值表示对应道路的长度,道路可以双向通行。
以顶点 为根。顶点 的管理区域定义为以 为根的整棵子树,包括 自己。
一个区域内的路线是一条完全位于该区域内的简单路径,即不能重复经过任何顶点。路线长度等于路径上所有边权之和。允许只包含一个顶点,此时长度为 。
你需要回答 次询问。每次询问给出两个顶点 ,保证 位于 的子树内。求:完全位于 的子树内,并且经过顶点 的最长简单路径的长度。
顶点 可以是路径的端点,也可以是内部顶点。
输入格式
第一行包含两个整数 。
接下来 行,每行包含三个整数 ,表示顶点 之间有一条长度为 的道路。保证这些道路构成一棵树。
接下来 行,每行包含两个整数 ,表示一次询问。注意输入顺序是先给必须经过的顶点 ,再给限定子树的根 。
输出格式
输出 行,每行一个整数,表示对应询问的答案。
答案可能超过 32 位有符号整数的范围。
样例输入
10 3
1 2 2
1 3 5
1 4 3
2 5 3
5 6 1
7 5 2
8 6 3
6 9 8
10 8 4
6 2
7 1
6 1
样例输出
15
12
19
数据范围与分组
- ;
- ;
- ;
- 对每次询问, 是 的祖先或 。
| 分值 | 额外限制 |
|---|---|
| 10 | 树是一条链,顶点 为顶点 的父亲,且所有边权为 |
| 根节点与其余所有节点直接相连,且所有边权为 | |
| 15 | |
| 所有询问满足 | |
| 35 | 无额外限制 |