Problem Description

You are given a tree with $n$ nodes. The tree edges have weights, and there is a sequence $a$ of length $n$.

Define the parent of node $x$ as $fa(x)$. The root $rt$ satisfies $fa(rt)=rt$.

Define the depth $dep(x)$ of node $x$ as the sum of all edge weights on the simple path from $x$ to the root.

There are $m$ operations:

1 l r: For all $l \le i \le r$, set $a_i := fa(a_i)$.

2 l r: Query, for all $l \le i \le r$, the minimum value of $dep(a_i)$.

Input Format

The first line contains three integers $n$ $m$ $rt$ separated by spaces, where $rt$ is the index of the root.

Then follow $n-1$ lines, each containing three integers $u,v,w$ separated by spaces, representing an edge between $u$ and $v$ with weight $w$.

Then one line contains $n$ integers separated by spaces, representing the sequence.

Then follow $m$ lines, each containing three integers separated by spaces, representing one operation.

Output Format

For each operation of type $2$, output one line with one integer representing the corresponding answer.

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

Hint

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

Constraints: For $100\%$ of the testdata, $1\le n,m\le 2\cdot 10^5$, $1\le a_i\le n$, and edge weights are in $[0,10^9]$.

Translated by ChatGPT 5