QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB
统计

给定一棵 $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

子任务

Idea:yummy,Solution:nzhtl1477&memset0,Code:nzhtl1477,Data:nzhtl1477

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