P14521 【MX-S11-T2】加减乘除

[想象一朵未来的玫瑰 - 贰零Levent / 星尘](https://music.163.com/song?id=2136583314)

给定一棵有 $n$ 个节点的树，节点编号为 $1 \sim n$，根节点为 $1$，每个点上有一个符号（加减号其中之一）$\mathrm{op}_i$ 和一个数 $a_i$，每条边都有一个区间 $[l, r]$。 你现在在节点 $1$，手中有一个数 $x$，你需要进行以下流程： - 假设你在节点 $u$，你将手中的数 $x$ 变为 $x \mathbin{\mathrm{op}_u} a_u$。 - 你可以选择在点 $u$ 结束流程，也可以选择一个子节点 $v$，假设连接 $u, v$ 的边的区间为 $[l, r]$，需要满足 $l \le x \le r$，然后走到 $v$ 并重复这两个步骤。 给定 $q$ 次询问，每次给出你手上的数的初值 $x$，你需要回答你能在上面结束流程的节点个数。

第一行，两个整数 $n,q$。 接下来 $n - 1$ 行，第 $i$ 行三个整数 $p_{i+1}, l_{i+1}, r_{i+1}$ 表示 $i + 1$ 的父亲为 $p_{i+1}$，连接它们的边的区间为 $[l_{i + 1}, r_{i + 1}]$。 接下来 $n$ 行，第 $i$ 行一个字符 $\mathrm{op}_i$ 与一个整数 $a_i$。 接下来 $q$ 行，每行一个整数 $x$。

输出 $q$ 行，每行一个整数，表示答案。

**【样例解释 #1】** 当 $x=1$ 时，能在节点 $1,2,5$ 上结束流程。 当 $x=2$ 时，能在节点 $1,2,3,4,5$ 上结束流程。 当 $x=3$ 时，能在节点 $1,2,3,4,5$ 上结束流程。 当 $x=4$ 时，能在节点 $1,2,3,5$ 上结束流程。 当 $x=5$ 时，能在节点 $1,3$ 上结束流程。 **【样例 #2】** 见选手目录下的 $\textbf{\textit{calc/calc2.in}}$ 与 $\textbf{\textit{calc/calc2.ans}}$。 该样例满足测试点 $1\sim 3$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{calc/calc3.in}}$ 与 $\textbf{\textit{calc/calc3.ans}}$。 该样例满足测试点 $4\sim 6$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{calc/calc4.in}}$ 与 $\textbf{\textit{calc/calc4.ans}}$。 该样例满足测试点 $7\sim 9$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{calc/calc5.in}}$ 与 $\textbf{\textit{calc/calc5.ans}}$。 该样例满足测试点 $10$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{calc/calc6.in}}$ 与 $\textbf{\textit{calc/calc6.ans}}$。 该样例满足测试点 $11\sim 20$ 的约束条件。 **【数据范围】** 本题共 $20$ 个测试点，每个 $5$ 分。 对于所有测试数据，保证： - $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} |测试点编号|$n \le$|$q \le$|特殊性质| |:-----:|:-:|:-:|:-:| | $1\sim 3$ | $10^3$ | $10^3$ | 无 | | $4\sim 6$ | $5\times 10^5$ | $10^6$ | A | | $7\sim 9$ | ^ | ^ | B | | $10$ | ^ | ^ | C | | $11\sim 20$ | ^ | ^ | 无 | - 特殊性质 A：对于所有 $2 \le i \le n$ 均有 $p_i=i-1$。 - 特殊性质 B：对于所有 $2 \le i \le n$ 均有 $l_i=-10^3$、$r_i=10^3$，并且对于所有 $1 \le i \le n$ 均有 $-10^3\le a_i \le 10^3$，并且 $-10^3\le x \le 10^3$。 - 特殊性质 C：对于所有 $1 \le i \le n$ 均有 $a_i=0$。