← 返回题目列表

AtCoder · tkppc6_2_i

I. 旅行者规划问题2

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

配点 : 700 点

問題文

P研王国有,1 减去 N 由 N 个城市,以及连接这些城市的 N-1 由一条主干道组成。i 真正的道路是城市 u_i 和 按字典顺序比较 v_i 双向道路,并且 0 以上 1 从以下整数中组成的权重 w_i 。

好了,从现在起,企鹅君将开始旅行P研王国。企鹅君的旅行 M+1 整数 给出了 x_0,x_1,\ldots,x_M 由表示,这是企鹅君从城市 x_0 出发,按顺序访问城市 x_1,x_2,\ldots,x_M (途中可以经过其他城市)。

企鹅君在旅行中,可以随意重复以下操作。

  • 从当前所在城市,选择与之直接通过道路连接的城市 1 个,通过道路移动到该城市。成本将加上经过道路的权重,随后经过的道路权重(x 记作) 1-x 将被替换为。

企鹅君想要在整个旅程中将总成本最小化。

顺便说一下,企鹅君非常任性。因此,请按照给出的顺序处理以下查询 Q 个。

  • 类型1:整数 a,b 。 表示x_a 该值应乘以 b 。
  • 类型2:整数 r 给出。当企鹅君按此顺序访问城市 x_0 开始 x_1,x_2,\ldots,x_r 时,求总成本的最小值。注意,类型2的查询是独立的,因此在移动过程中边的权重的变化不在后续查询中考虑。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq u_i,v_i \leq N\ (1 \leq i \leq N-1)
  • 0 \leq w_i \leq 1\ (1 \leq i \leq N-1)
  • 1 \leq x_i \leq N\ (0 \leq i \leq M)
  • 在类型1查询中,0 \leq a \leq M,1 \leq b \leq N 成立
  • 在类型2查询中,1 \leq r \leq M 成立
  • 每个查询的前后,x_i \neq x_{i+1}\ (0 \leq i \leq M-1) 成立
  • Q 第 个查询是类型2查询
  • 给定的图是一棵树
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M Q
u_1 v_1 w_1
u_2 v_2 w_2
\hspace{0.8cm}\vdots
u_{N-1} v_{N-1} w_{N-1}
x_0 x_1 \ldots x_M
\text{query}_1
\text{query}_2
\hspace{0.4cm}\vdots
\text{query}_Q

这里 \text{query}_i 是 您也可以写 i 个查询的内容如下所示,分别以以下格式给出。

  • \text{type}=1 表示该查询是类型1,输入格式如下。
\text{type} a b
  • \text{type}=2 表示该查询是类型2,输入格式如下。
\text{type} r

出力

每当给出类型2查询时,请输出问题中所问的值,并换行。


入力例 1

3 3 3
1 2 0
1 3 1
1 3 2 3
2 2
1 2 1
2 3

出力例 1

1
2

1 在第几个查询中,企鹅君应按照顶点 1 \rightarrow 頂点 3 \rightarrow 頂点 1 \rightarrow 頂点 2 的顺序移动。移动所需的成本分别为 1, 0, 0 ,所以答案是 1 。

3 在第几个查询中,企鹅君应按照顶点 1 \rightarrow 頂点 3 \rightarrow 頂点 1 \rightarrow 頂点 3 的顺序移动。移动所需的成本分别为 1, 0, 1, 0 ,所以答案是 2 。


入力例 2

5 10 8
1 2 0
3 1 0
2 4 0
5 4 1
1 3 4 2 5 3 1 3 4 2 4
1 2 1
1 6 2
2 5
1 6 4
2 9
2 8
1 7 1
2 2

出力例 2

4
9
8
1

原案: 企鹅人