P12536 [XJTUPC 2025] Seele Vollerei

**Please note the unusual space constraints for this problem.** Given $\textbf{an operation sequence}$ $A$ and a rooted tree $T$, each operation in $A$ is like ''add $x$ to all point weights on the simple path from $u$ to $v$ in $T$.'' The simple path from $u$ to $v$ is defined as a path starting from $u$ and ending at $v$ that does not repeatedly visit any nodes or edges. Initially, the root of $T$ is $1$, and all point weights are $0$. You need to perform three operations: - Given an interval $[l,r]$, perform operations from $A_l, A_{l+1}\dots$ to $A_r$ in sequence; - Query the sum of the subtrees of $T$ with $x$ as the root; - Change the root of $T$ to $y$ (If the current root is $y$, no operation will be performed).

The first line contains three positive integers $n_1$, $n_2$, and $m$ ($1\le n_1,n_2,m \le 1\times 10^5$), separated by a space, representing the length of $A$, the total number of points in $T$, and the number of inquiries and operations. The next $n_1$ lines, the $i$-th line contains three integers $u_i$, $v_i$, and $x_i$ ($1\le u_i,v_i\le n_2, 1\le x_i\le 1\times 10^2$), separated by a space, representing the operation $A_i$ as ''add $x_i$ to all point weights on the simple path from $u_i$ to $v_i$ in $T$.'' Next, there are $n_2-1$ lines, each containing two positive integers $u$ and $v$ ($1\le u,v \le n_2$), separated by a space, representing an edge of the tree. It is guaranteed that the $n_2-1$ edges form a tree. Next, there are $m$ lines. The first number $op$ ($op\in \{1,2,3\}$) in each line indicates the operation number, followed by: - If $op$ is $1$, it is followed by two positive integers $l$ and $r$ ($1\le l\le r\le n_1$), separated by a space, indicating that the operations of $A_l, A_{l+1} \dots A_r$ are executed in sequence; - If $op$ is $2$, it is followed by a positive integer $x$ ($1\le x\le n_2$), indicating that the sum of the subtrees of $T$ with $x$ as the root is queried; - If $op$ is $3$, it is followed by a positive integer $y$ ($1\le y\le n_2$), indicating that the root of $T$ is changed to $y$ (If the current root is $y$, no operation will be performed).

For each operation $2$, output one line of one integer, representing the sum of the subtrees of $T$ with $x$ as the root. The data ensures that the answer is within the range expressed by a signed long long integer.