#1868. 皮鞋的多项式

    ID: 1868 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1826来源:qoj.ac数据:公开样例树上算法线段树

皮鞋的多项式

皮鞋的多项式

题目描述

标题: 皮鞋的多项式 - Problem - QOJ.ac

#9608. 皮鞋的多项式

Statistics

The problem was used in the following contests:

皮鞋有一颗 n 个节点的有根树,其中 1 号节点为根节点。

皮鞋很喜欢多项式,所以他在每个节点上都写了一个多项式。

有一天钥匙看到了皮鞋的这棵树。对于一个节点 x,钥匙定义 F(x) 为 x 子树内所有节点上多项式的乘积。现在钥匙给了你 q 个询问,每个询问形如 x l r,你需要告诉钥匙 (∑i=lr[xi]F(x))mod998244353 的值。

由于钥匙急切地想知道答案,所以询问强制在线。

输入格式

第一行两个正整数 n,q 表示树的节点数与询问个数。

接下来 n 行,第 i 行的第一个整数 ki−1 表示 i−1 号节点的多项式次数。接下来 ki−1+1 个数 ai−1,0∼ai−1,ki−1 以此表示这个多项式第 0∼ki−1 次项的系数。

接下来 n−1 行每行两个正整数 u,v 表示树上的一条边。

接下来 q 行每行 3 个整数 x′,l′,r′ 表示一组询问。真实的询问 x=x′xor⁡lastans,l=l′xor⁡lastans,r=r′xor⁡lastans,其中 lastans 为上一组询问的答案,若没有上一组询问则 lastans 为 0。

输出格式

输出 q 行,表示每组询问的答案。

样例 1

样例 1 输入

3 6
1 1 1 
1 1 1 
1 1 1 
1 2
2 3
1 0 3
10 9 10
0 3 0
3 3 3
1 1 1
2 2 2

样例 1 输出

8
3
2
3
1
0

样例 1 解释

解密后的输入为:

3 6
1 1 1
1 1 1
1 1 1
1 2
2 3
1 0 3
2 1 2
3 0 3
1 1 1
2 2 2
3 3 3

其中 F(3)=1+x,F(2)=1+2x+x2,F(1)=1+3x+3x2+x3。

数据范围

对于 100% 的数据,满足 1≤n≤105,0≤ki,∑ki≤105,1≤q≤2×105,1≤u,v,x≤n,0≤l≤r≤∑ki,0≤ai,j≤998244352。

子任务

子任务编号 特殊性质 分值 1 n,∑ki≤2000 7 2 ∑ki=0 3 3 x=1 20 4 n,q≤5×104,ki=1 20 5 n,q,∑ki≤2×104 20 6 无特殊限制 30

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 6
1 1 1 
1 1 1 
1 1 1 
1 2
2 3
1 0 3
10 9 10
0 3 0
3 3 3
1 1 1
2 2 2
8
3
2
3
1
0