#P17308. 又一个树上问题

    ID: 16422 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>组合数学多项式与生成函数FFTCF2700树形DP多项式

又一个树上问题

题目描述

给定一棵以 11 号节点为根的树,共有 nn 个节点。

每个节点 ii 上维护两个整数:

  • 当前值 cic_i,其中 ci≥0c_i\ge 0;
  • 模数 did_i,其中 di>0d_i>0。

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

每次操作需要选择一个节点 uu,并且必须满足当前的 cuc_u 不是 dud_u 的倍数,即 cu mod du≠0c_u\bmod d_u\ne 0。随后,将从节点 uu 到根节点 11 的简单路径上所有节点 vv 的 cvc_v 同时增加 11。

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

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

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

输入格式

第一行一个整数 nn,表示树的节点数。

接下来 nn 行,第 ii 行两个整数 ci,dic_i,d_i,表示节点 ii 的初始值和模数。

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

树的根固定为节点 11。

输出格式

输出一个整数,表示能够得到的不同最终 cc 数组数量对 998244353998244353 取模后的结果。

样例输入

2
0 2
1 2
1 2

样例输出

3

样例说明

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

  • 不进行任何操作,可以得到 (0,1)(0,1);
  • 对节点 22 操作一次,可以得到 (1,2)(1,2);
  • 此时节点 11 满足 1 mod 2≠01\bmod 2\ne0,再对节点 11 操作一次,可以得到 (2,2)(2,2)。

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

数据范围

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

子任务 分值 限制
1 10 m≤1m\le1
2 15 n≤10n\le10,di≤3d_i\le3
3 10 m≤2m\le2
4 20 n≤50n\le50,满足特殊性质 A
5 n≤400n\le400
6 25 无额外限制

特殊性质 A:对于每个 2≤i≤n2\le i\le n,节点 ii 的父亲从 1,2,…,i−11,2,\ldots,i-1 中等概率随机选取。

对于所有数据:

  • 1≤n≤20001\le n\le2000;
  • 0≤ci≤1090\le c_i\le10^9;
  • 1≤di≤1091\le d_i\le10^9。