配点 : 1500 点
問題文
N 给定一个带根的树的顶点。 每个顶点都带有 1, \, 2, \, ..., \, N 的编号,并且边 1 是这棵带根树的根。 i(1 ≦ i ≦ N-1) 边是边界 A_i 和顶点 连接 B_i 连接的、长度为 C_i 的无向边。
Q 个查询会被给出,请按顺序处理。 查询有 2 种,输入格式和查询内容如下。 在以
1 v k x: 頂点 v 为根的子树中, 第k 条边和 k+1 代的顶点所连接的每一条边的长度上加上 x 。这里,边缘被定义为第 v 表示 1 代的边缘,并且属于第n 代顶点的直接子节点的顶点是 n+1 被定义为代目的边缘。2 u v: 頂点 u 到顶点 这意味着可以通过沿着边缘到达 v 求到达的最短路径长度。
详细请参考样本 1 进行确认。
制約
- 1 ≦ N, \, Q ≦ 10^{5}
- 1 ≦ A_i, \, B_i ≦ N
- 1 ≦ C_i ≦ 10^{5}
- 1 ≦ u, \, v, \, k ≦ N
- 1 ≦ x ≦ 10^5
- 所提供的图形是木的
- 種類 2 的查询给出的顶点 u, \, v 是不同的
- C_i, \, x 均为整数 每个查询的答案均采用
入力
输入将以以下格式从标准输入提供。
N
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
Query_1
:
Query_{Q}
出力
2 u v格式,按照查询的顺序显示。 1 逐行输出。
入力例 1
6 1 2 4 1 4 2 4 3 7 4 5 3 2 6 2 5 1 1 2 5 2 3 5 1 4 1 2 2 6 3 2 2 4
出力例 1
20 27 6
首先,您将获得如下图所示的图表。 处理查询
1 1 2 5后,边长变化如下图所示。2 下一个顶点的顶点
连接边的长度 2, \, 4 和 3 下一个顶点的顶点
连接边的长度 3, \ 5, \ 6 添加了 5 。
此外,1 4 1 2后,边长变化如下图所示。1 下一个顶点的顶点
连接边的长度 4 和 2 下一个顶点的顶点
连接边的长度 3, \, 6 添加了 2 。
入力例 2
2 1 2 1 3 1 1 2 10 1 2 2 5 2 1 2
出力例 2
1
不保证要添加的边存在。