You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵 $n$ 个节点的树，树有边权，与一个长为 $n$ 的序列 $a$。

定义节点 $x$ 的父亲为 $fa(x)$，根 $rt$ 满足 $fa(rt)=rt$。

定义节点 $x$ 的深度 $dep(x)$ 为其到根简单路径上所有边权和。

有 $m$ 次操作：

1 l r：对于 $l \le i \le r$， $a_i := fa(a_i)$ 。

2 l r ：查询对于 $l \le i \le r$，最小的 $dep(a_i)$。

输入格式

第一行三个空格隔开的数 $n$ $m$ $rt$，其中 $rt$ 表示根节点的编号。

之后 $n-1$ 行，每行三个空格隔开的数 $u,v,w$ 表示一条 $u$ 与 $v$ 之间，边权为 $w$ 的边。

之后一行 $n$ 个空格隔开的数表示这个序列。

之后 $m$ 行，每行三个用空格隔开的数，表示一次操作。

输出格式

对每个 $2$ 操作，输出一行一个数表示其对应的答案。

5 6 2
3 2 2
5 3 3
1 2 4
4 2 3
3 3 3 1 2
2 1 1
2 2 3
2 4 5
1 2 3
1 4 4
2 1 2

2
2
0
0

提示

对于 $100\%$ 的数据，$1\le n,m\le 2\cdot 10^5$，$1\le a_i\le n$，边权在 $[0,10^9]$ 之间。