#P6785. [2019福建夏令营]树
[2019福建夏令营]树
树(tree)
题目描述
给定一棵有 个节点的带权树,节点编号为 到 。
有 次询问。每次给定 ,求从节点 到编号属于区间 的节点的最短距离,即
两点的距离为连接它们的唯一路径上所有边长之和。如果 ,则答案为 。
输入格式
第一行一个正整数 。
接下来 行,每行三个正整数 ,表示节点 与节点 之间有一条长度为 的边。
接下来一行一个正整数 。
接下来 行,每行三个正整数 ,描述一次询问,其中 ,。
输出格式
输出 行,每行一个整数,表示对应询问的答案。
样例输入
3
1 2 1
1 3 1
3
2 3 1
2 3 2
3 3 2
样例输出
1
0
2
数据范围
- 对于 的数据,。
- 另有 的数据,节点 到 均与节点 有边相连。
- 另有 的数据,对所有 ,节点 与节点 有边相连。
- 对于所有数据,,任意两点之间的距离不超过 。