#P9709. 动态半平面交
动态半平面交
题目描述
给定一棵以 号点为根的树,第 个点的权值为 。每次询问给出 ,求 的子树中所有与 距离不超过 的顶点的点权最小公倍数,对 取模。距离按路径的边数计算,子树包括点 自身。
输入格式
第一行两个整数 ,分别为在线参数和点数。第二行 个正整数 。随后 行,每行两个正整数,表示树的一条边。
接下来一行一个正整数 。随后 行,每行两个非负整数,读入为 。用上一次输出 解码,初始 。
$$u=u'\mathbin{\oplus}(k\cdot lastans),\qquad d=d'\mathbin{\oplus}(k\cdot lastans).$$其中 表示按位异或。解码后 且 。全部本站数据满足 。
输出格式
每次询问输出一行,表示最小公倍数取模后的结果。
样例
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。
数据范围
对于全部数据,,,。
- 对于 5% 的数据,。
- 对于 20% 的数据, 且 。
- 另有 20% 的数据,每条边按输入顺序给出的端点满足 。
- 另有 20% 的数据,。