P17340 [MX-X30-T6] Cuckoo Clock

You are right, but a certain four-character game is indeed fun.

You have a rooted tree with root $1$. At node $i$, there is a non-negative integer $c_i$ and a positive integer $d_i$. You may perform the following operation any number of times: - Choose a node $u$ such that $c_u$ is **not** a multiple of $d_u$. Then increase $c_i$ by $1$ for all nodes $i$ on the path from $u$ to the root (including both $u$ and the root). After performing these operations, find the number of essentially different arrays $c$, modulo $998244353$.

The first line contains an integer $n$. The next $n$ lines each contain two integers $c_i, d_i$. The next $n - 1$ lines each contain two integers $u_i, v_i$, indicating an edge.

Output a single integer, representing the number of essentially different arrays $c$ modulo $998244353$.

Let $m$ be the distance from the farthest node to the root. | Subtask | Score | Constraints | | :-----: | :---: | :---------: | | 1 | $10$ | $m \le 1$ | | 2 | $15$ | $n \le 10$，$d_i \le 3$ | | 3 | $10$ | $m \le 2$ | | 4 | $20$ | $n \le 50$，Special Property A | | 5 | $20$ | $n \le 400$ | | 6 | $25$ | None | Special Property A: It is guaranteed that for $2 \le i \le n$, the parent of node $i$ in the rooted tree is generated uniformly at random from $1 \sim i - 1$. Constraints: For all testdata, $1 \le n \le 2000$, $0 \le c_i \le 10^9$, $1 \le d_i \le 10^9$. Translated by ChatGPT 5