P6779 [Ynoi2009] rla1rmdq

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)$.

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.

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

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