P17340 【MX-X30-T6】布谷鸟钟

你说的对，但是某四字游戏确实好玩。

你有一棵以 $1$ 为根的有根树。 第 $i$ 个点上有一个非负整数 $c_i$ 和一个正整数 $d_i$。你可以进行若干次如下操作： + 选择一个点 $u$，满足 $c_u$ **不是** $d_u$ 的倍数。然后令 $u$ 到根上的所有数的 $c_i$ 增加 $1$。 求执行完这些操作后，本质不同的 $c$ 数组的个数对 $998244353$ 取模的结果。

第一行包含一个整数 $n$。 接下来 $n$ 行，第 $i$ 行两个整数 $c_i,d_i$。 接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示一条边。

输出包含一个整数，表示本质不同的 $c$ 数组的个数对 $998244353$ 取模的结果。

设 $m$ 为距离根最远的点到根的距离。 | 子任务 | 分数 | 限制 | | :----: | :---: | :----------------: | | 1 | $10$ | $m\le 1$ | | 2 | $15$ | $n\le 10$，$d_i\le 3$ | | 3 | $10$ | $m\le 2$ | | 4 | $20$ | $n\le 50$，特殊性质 A | | 5 | $20$ | $n \le 400$ | | 6 | $25$ | 无 | 特殊性质 A：保证对于 $2\le i\le n$，点 $i$ 在有根树上的父亲在 $1\sim i-1$ 中等概率随机生成。 对于所有数据，$1\le n\le 2000$，$0\le c_i\le 10^9$，$1\le d_i\le 10^9$。