P14521 [MX-S11-T2] Addition, Subtraction, Multiplication, and Division.

[Imagine a Future Rose - 20 Levent / Xingchen](https://music.163.com/song?id=2136583314).

You are given a tree with $n$ nodes, numbered from $1$ to $n$. The root is node $1$. Each node has an operator (either plus or minus) $\mathrm{op}_i$ and a number $a_i$. Each edge has an interval $[l, r]$. You start at node $1$ with a number $x$ in your hand, and you need to perform the following process: - Suppose you are at node $u$. You change the number in your hand from $x$ to $x \mathbin{\mathrm{op}_u} a_u$. - You may choose to end the process at node $u$, or you may choose a child node $v$. Suppose the interval on the edge connecting $u$ and $v$ is $[l, r]$. You must satisfy $l \le x \le r$, then move to $v$ and repeat these two steps. You are given $q$ queries. In each query, you are given the initial value of $x$ in your hand. You need to answer how many nodes you can end the process at.

The first line contains two integers $n, q$. The next $n - 1$ lines: in the $i$-th line there are three integers $p_{i+1}, l_{i+1}, r_{i+1}$, meaning the parent of node $i + 1$ is $p_{i+1}$, and the interval on the edge connecting them is $[l_{i + 1}, r_{i + 1}]$. The next $n$ lines: in the $i$-th line there is a character $\mathrm{op}_i$ and an integer $a_i$. The next $q$ lines: each line contains an integer $x$.

Output $q$ lines, each line contains one integer, representing the answer.

**Sample Explanation #1** When $x = 1$, you can end the process at nodes $1, 2, 5$. When $x = 2$, you can end the process at nodes $1, 2, 3, 4, 5$. When $x = 3$, you can end the process at nodes $1, 2, 3, 4, 5$. When $x = 4$, you can end the process at nodes $1, 2, 3, 5$. When $x = 5$, you can end the process at nodes $1, 3$. **Sample #2** See $\textbf{\textit{calc/calc2.in}}$ and $\textbf{\textit{calc/calc2.ans}}$ in the contestant directory. This sample satisfies the constraints of test points $1 \sim 3$. **Sample #3** See $\textbf{\textit{calc/calc3.in}}$ and $\textbf{\textit{calc/calc3.ans}}$ in the contestant directory. This sample satisfies the constraints of test points $4 \sim 6$. **Sample #4** See $\textbf{\textit{calc/calc4.in}}$ and $\textbf{\textit{calc/calc4.ans}}$ in the contestant directory. This sample satisfies the constraints of test points $7 \sim 9$. **Sample #5** See $\textbf{\textit{calc/calc5.in}}$ and $\textbf{\textit{calc/calc5.ans}}$ in the contestant directory. This sample satisfies the constraints of test point $10$. **Sample #6** See $\textbf{\textit{calc/calc6.in}}$ and $\textbf{\textit{calc/calc6.ans}}$ in the contestant directory. This sample satisfies the constraints of test points $11 \sim 20$. **Constraints** There are $20$ test points in this problem, each worth $5$ points. For all testdata, it is guaranteed that: - $1 \le n \le 5 \times 10^5$. - $1 \le q \le 10^6$. - $-10^{18} \le l_i \le r_i \le 10^{18}$. - $-10^{18} \le x, a_i \le 10^{18}$. - $\mathrm{op}_i \in \{ +, - \}$. - $1 \le p_i < i$. ::cute-table{tuack} | Test Point ID | $n \le$ | $q \le$ | Special Property | |:-----:|:-:|:-:|:-:| | $1 \sim 3$ | $10^3$ | $10^3$ | None | | $4 \sim 6$ | $5 \times 10^5$ | $10^6$ | A | | $7 \sim 9$ | ^ | ^ | B | | $10$ | ^ | ^ | C | | $11 \sim 20$ | ^ | ^ | None | - Special Property A: For all $2 \le i \le n$, $p_i = i - 1$. - Special Property B: For all $2 \le i \le n$, $l_i = -10^3$ and $r_i = 10^3$. Also, for all $1 \le i \le n$, $-10^3 \le a_i \le 10^3$, and $-10^3 \le x \le 10^3$. - Special Property C: For all $1 \le i \le n$, $a_i = 0$. Translated by ChatGPT 5