#P9709. 动态半平面交

    ID: 6333 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-最小公倍数线性筛最小质因子预处理查询排序子树转区间贡献法LCA树上倍增有序集合增量维护模逆元普通线段树

动态半平面交

题目描述

给定一棵以 11 号点为根的树,第 ii 个点的权值为 aia_i。每次询问给出 u,du,d,求 uu 的子树中所有与 uu 距离不超过 dd 的顶点的点权最小公倍数,对 998244353998244353 取模。距离按路径的边数计算,子树包括点 uu 自身。

输入格式

第一行两个整数 k,nk,n,分别为在线参数和点数。第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n。随后 n−1n-1 行,每行两个正整数,表示树的一条边。

接下来一行一个正整数 qq。随后 qq 行,每行两个非负整数,读入为 u′,d′u',d'。用上一次输出 lastanslastans 解码,初始 lastans=0lastans=0。

$$u=u'\mathbin{\oplus}(k\cdot lastans),\qquad d=d'\mathbin{\oplus}(k\cdot lastans).$$

其中 ⊕\oplus 表示按位异或。解码后 1≤u≤n1\le u\le n 且 d≥0d\ge0。全部本站数据满足 k=0k=0。

输出格式

每次询问输出一行,表示最小公倍数取模后的结果。

样例

0 5
4 6 3 2 7
1 2
1 3
3 4
3 5
2
1 2
3 0
84
3

附加样例 输入 2、输出 2、输入 3、输出 3、输入 4、输出 4。

数据范围

对于全部数据,1≤n,q≤1051\le n,q\le10^5,1≤ai≤1071\le a_i\le10^7,k=0k=0。

  • 对于 5% 的数据,n,q≤100n,q\le100。
  • 对于 20% 的数据,k=0k=0 且 n,q≤30000n,q\le30000。
  • 另有 20% 的数据,每条边按输入顺序给出的端点满足 v=u+1v=u+1。
  • 另有 20% 的数据,ai≤na_i\le n。

原 PDF