P1064A 病毒（cancer）

【题目背景】

A 病毒席卷了 Gioush 大队！

【题目描述】

A 病毒在 Gioush 大队的 $n$ 个营地中肆虐，Gioush 大队的 $n$ 个营地的结构是一棵以 $1$ 号营地为根节点的有根树结构。

A 病毒与普通病毒不同，它会将沿途获得的每一条信息保存在自己的记忆中，并据此不断调整之后的传播策略。记录越多，它看似越能理解各个营地，行动时却也必须同时遵守越来越多的限制。

对于 $2\leq i\leq n$，$i$ 号营地的父亲为 $p_i$ 号营地。记 $d_i$ 为从 $i$ 号营地前往 $1$ 号营地需要经过的道路数量，则 $d_1=0$，对于 $2\leq i\leq n$，有 $d_i=d_{p_i}+1$。

A 病毒希望从某个 $2\sim n$ 号营地开始传播，最终侵入 $1$ 号营地。将这样一次传播的过程称为一条感染路线。当 A 病毒位于 $i$ 号营地时，可以进行以下两种行动之一：

1. 上行感染：在给定的范围 $[l_i,r_i]$ 中选择一个整数 $k$，沿着前往 $1$ 号营地的方向传播 $k$ 步，也就是直接到达 $i$ 号营地的 $k$ 级祖先。保证 $1\leq l_i\leq r_i\leq d_i$。
2. 下行扩散：选择 $i$ 号营地的一个儿子并传播到该营地。特别地，当 $i$ 号营地是叶子时，A 病毒无法进行下行扩散。

一条感染路线中，A 病毒最初所在的营地与每次行动后到达的营地依次构成这条路线的感染序列。形式化地说，从 $x$ 号营地开始的一条感染路线对应一个序列 $a_1=x,a_2,\cdots,a_m=1$。对于每个 $1\leq i<m$，要么存在 $l_{a_i}\leq k\leq r_{a_i}$，使得 $a_{i+1}$ 是 $a_i$ 的 $k$ 级祖先，要么有 $p_{a_{i+1}}=a_i$。

所幸，Gioush 大队早已为每个 $2\sim n$ 号营地准备了防疫装置，其中 $i$ 号营地的防疫强度为 $h_i$。A 病毒每经过一个营地，这个营地的防疫装置就会启动。此后，A 病毒若再次进行上行感染，就必须越过此前经过的每个营地所能封锁的范围。

具体地说，一条感染路线合法，当且仅当对于其感染序列中的任意 $1\leq i<j\leq m$，若 A 病毒由 $a_{j-1}$ 号营地通过上行感染到达 $a_j$ 号营地，则必须满足 $d_{a_j}<d_{a_i}-h_{a_i}$。保证对于每个 $2\leq i\leq n$，均有 $0\leq h_i<d_i$。

对于每个 $2\sim n$ 号营地，请你分别求出从该营地开始、最终侵入 $1$ 号营地的合法感染路线数量。两条感染路线不同，当且仅当它们对应的感染序列不同。

由于答案可能很大，你只需要输出答案对 $998{,}244{,}353$ 取模后的结果。

【输入格式】

从文件 $\textbf{\textit{cancer.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含一个整数 $n$，表示营地的数量。

接下来 $n-1$ 行，第 $i-1$ 行包含四个整数 $p_i,l_i,r_i,h_i$，依次表示 $i$ 号营地的父亲、进行上行感染时可以选择的步数下界与上界，以及 $i$ 号营地的防疫强度。

【输出格式】

输出到文件 $\textbf{\textit{cancer.out}}$ 中。

对于每组测试数据，输出一行 $n-1$ 个整数，其中第 $i-1$ 个整数表示从 $i$ 号营地开始的合法感染路线数量对 $998{,}244{,}353$ 取模后的结果。

【样例 1 输入】

10 32531 1 1 042 1 1 052 1 2 164 2 3 07681 1 1 092 1 2 0103 1 3 2114 1 4 1125 1 5 3136141 1 1 0152 1 2 0162 1 2 0173 1 2 0183 2 3 2

【样例 1 输出】

13 3 2 425 9 3 21 634 10 5 14 1

【说明/提示】

【样例 1 解释】

对于第一组测试数据，从 $4$ 号营地开始的合法感染路线共有 $2$ 条，其感染序列分别为 $[4,1]$ 与 $[4,5,1]$。从 $5$ 号营地开始的合法感染路线共有 $4$ 条，其感染序列分别为 $[5,1]$、$[5,2,1]$、$[5,2,4,1]$ 与 $[5,2,4,5,1]$。

因此，从 $2\sim 5$ 号营地开始的合法感染路线数量依次为 $3,3,2,4$。

【样例 2】

见选手目录下的 $\textbf{\textit{cancer/cancer2.in}}$ 和 $\textbf{\textit{cancer/cancer2.ans}}$。

该组样例符合测试点 $1\sim 2$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{cancer/cancer3.in}}$ 和 $\textbf{\textit{cancer/cancer3.ans}}$。

该组样例符合测试点 $3\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{cancer/cancer4.in}}$ 和 $\textbf{\textit{cancer/cancer4.ans}}$。

该组样例符合测试点 $9\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{cancer/cancer5.in}}$ 和 $\textbf{\textit{cancer/cancer5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{cancer/cancer6.in}}$ 和 $\textbf{\textit{cancer/cancer6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$2\leq n\leq 2\times 10^3$。对于同一个测试点，保证 $\sum n\leq 2\times 10^3$。对于任意 $2\leq i\leq n$，保证 $1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。

特殊性质 A：对于任意 $2\leq i\leq n$，均有 $h_i=0$。

特殊性质 B：对于任意 $2\leq i\leq n$，均有 $p_i=i-1$。