[MX-X30-T6] 布谷鸟钟

题目描述

给定一棵以 $1$ 号节点为根的树，共有 $n$ 个节点。

每个节点 $i$ 上维护两个整数：

• 当前值 $c_i$，其中 $c_i\ge 0$；
• 模数 $d_i$，其中 $d_i>0$。

你可以进行任意次操作，也可以一次操作都不进行。

每次操作需要选择一个节点 $u$，并且必须满足当前的 $c_u$ 不是 $d_u$ 的倍数，即 $c_u\bmod d_u\ne 0$。随后，将从节点 $u$ 到根节点 $1$ 的简单路径上所有节点 $v$ 的 $c_v$ 同时增加 $1$。

你可以在任意时刻停止操作。

如果两种操作过程结束后得到的数组 $(c_1,c_2,\ldots,c_n)$ 不同，则认为它们得到的最终状态不同；如果最终数组完全相同，则只计为一种状态。

请计算从初始状态出发，能够得到多少种不同的最终 $c$ 数组。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$，表示树的节点数。

接下来 $n$ 行，第 $i$ 行两个整数 $c_i,d_i$，表示节点 $i$ 的初始值和模数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树中存在一条连接节点 $u$ 和节点 $v$ 的无向边。

树的根固定为节点 $1$。

输出格式

输出一个整数，表示能够得到的不同最终 $c$ 数组数量对 $998244353$ 取模后的结果。

样例输入

2
0 2
1 2
1 2

样例输出

3

样例说明

初始数组为 $(0,1)$。

• 不进行任何操作，可以得到 $(0,1)$；
• 对节点 $2$ 操作一次，可以得到 $(1,2)$；
• 此时节点 $1$ 满足 $1\bmod 2\ne0$，再对节点 $1$ 操作一次，可以得到 $(2,2)$。

因此一共可以得到 $3$ 种不同的最终数组。

数据范围

设 $m$ 为树中距离根节点最远的节点到根的边数。

特殊性质 A：对于每个 $2\le i\le n$，节点 $i$ 的父亲从 $1,2,\ldots,i-1$ 中等概率随机选取。

对于所有数据：

• $1\le n\le2000$；
• $0\le c_i\le10^9$；
• $1\le d_i\le10^9$。