← 返回题目列表

AtCoder · kupc2015_j

J. MOD查询

中文机器翻译题面 查看原题

問題文

頂点数 n 和顶点 i (i = 1, ..., n) 是正整数 写入 a_i 。 回答 q问题。

每个问题由三个整数组成, j 第一个问题是 它由 x_j, v_j, w_j 给出。
树顶 写入到 v_j 它们的编号最大为 w_j 的最短路径的顶点处的数字 a_i 按顺序打印除 x_j 的余数。 换句话说, 到v_j 它们的编号最大为 w_j 的最短路径是 p_1, ..., p_k (頂点数 k , p_1 = v_j, p_k = w_j ),然后 ((...((x_j % a_{p_1}) % a_{p_2}) ...) % a_{p_{k-1}} ) % a_{p_k} 输出。

但是 这是除以 x % y 表示 x 的 y 后取余数的运算。


入力

第一行是序列的长度 n 和问题数量 给出 q 。 第二行是一个数字序列 代表 a 代表 n 正整数以空格分隔。 继续 n-1 每行包含树边的端点。 b_i, c_i 用空格分隔。 继续 每个问题都在 q 行中给出。 每个问题由 3 个整数组成 x_j, v_j, w_j 用空格分隔。
n q
a_1 ... a_n
b_1 c_1
:
b_{n-1} c_{n-1}
x_1 v_1  w_1
:
x_q v_q  w_q
  • 1 \leq n \leq 100000
  • 1 \leq q \leq 100000
  • 1 \leq a_i \leq 10^{9}
  • 1 \leq b_i, c_i \leq n
  • 0 \leq x_j \leq 10^{9}
  • 1 \leq v_j, w_j \leq n
  • 所有输入值均为整数
  • 给定的图是一棵树

出力

输出是 第 q 行组成。 j 在线 一个整数,表示住在 j 将问题的答案打印为整数。

部分点

如果满足以下约束的数据集的所有答案都是正确的, 30 给出了点的部分点。

  • 全部 i (1 \leq i \leq n-1) , b_i = i, c_i = i+1 ,即图是一条路径
  • 全部 j (1 \leq j \leq q) , v_j \leq w_j 是


入力例1

5 2
8 6 4 3 2
1 2
2 3
3 4
4 5
15 1 5
15 2 5

出力例1

1
0
图具有路径结构。 关于第一个问题, 15 % 8 = 7, 7 % 6 = 1, 1 % 4 = 1, 1 % 3 = 1, 1 % 2 = 1 答案是 1 。 关于第二个问题, 15 % 6 = 3, 3 % 4 = 3, 3 % 3 = 0, 0 % 2 = 0 答案是 0 。从

入力例2

8 5
18 29 52 64 4 59 89 15
1 2
1 3
1 4
2 5
3 6
3 7
4 8
99 6 7
102 5 8
15 2 6
84 7 8
19 1 1

出力例2

40
2
15
14
1