#ABC070D. Transit Tree Path
Transit Tree Path
题目描述
You are given a tree with vertices.
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with edges, where is the number of its vertices.
The -th edge connects Vertices and , and has a length of .
You are also given queries and an integer . In the -th query :
- find the length of the shortest path from Vertex and Vertex via Vertex .
给你一棵有 个顶点的树。
这里,"树 "是一种图,更具体地说,是一个有 条边的连通无向图,其中 是其顶点数。
连接顶点 和 的 条边 的长度为 。我们还给出了 个查询和一个整数 。在 -th 查询 中:
- 求顶点 和顶点 经过顶点 的最短路径长度。
输入格式
输入内容按以下格式标准输入:
输出格式
以 行打印对查询的回复。
在 -th 第 行,打印对 -th 查询的响应。
样例 #1
样例输入 #1
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5
样例输出 #1
3
2
4
样例 #2
样例输入 #2
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7
样例输出 #2
5
14
22
样例 #3
样例输入 #3
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10
样例输出 #3
17000000000
说明
数据规模与约定
- 给定的图形是一棵树。
样例 解释
三个查询的最短路径如下:
- 查询 :顶点 → 顶点 .顶点 →顶点 。顶点 → 顶点 → 顶点 :长度
- 查询 :顶点 → 顶点 → 顶点 : 长度
- 查询 :顶点 → 顶点 {4419797} : 长度 。→ 顶点 顶点 → 顶点 顶点 → 顶点 → 顶点 : 长度
样例 解释
每个查询的路径必须经过顶点 。