← 返回题目列表

AtCoder · ddcc_2016_final_e

E. 有根树和查询

中文机器翻译题面 查看原题

配点 : 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

首先,您将获得如下图所示的图表。 处理查询

14719568c70b794384d9267713fc28f1.png

1 1 2 5后,边长变化如下图所示。2 下一个顶点的顶点 连接边的长度 2, \, 4 和 3 下一个顶点的顶点 连接边的长度 3, \ 5, \ 6 添加了 5 。

344f145215af530aec7fe65e98c2ec9c.png

此外,1 4 1 2后,边长变化如下图所示。1 下一个顶点的顶点 连接边的长度 4 和 2 下一个顶点的顶点 连接边的长度 3, \, 6 添加了 2 。

293c37ff6545b9d841490366cc4f1153.png

入力例 2

2
1 2 1
3
1 1 2 10
1 2 2 5
2 1 2

出力例 2

1

不保证要添加的边存在。