QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 256 MB Total points: 100
[-43]
统计

n 个节点,第 x 个节点有点权 ax,有两棵树分别独立地连接了这 n 个点,两棵树点权是共用的。

你需要进行 m 次操作,每次操作给定 x,y,k,进行以下两步:

  1. 将第一棵树上 x,y 之间最短路径上所有节点的点权增加 k
  2. 求第二棵树上 x,y 之间最短路径上的点权和对 264 取模的结果。

输入格式

第一行两个数 n,m,表示节点数和操作数。

第二行 n 个数,第 x 个数表示 ax,即节点 x 的初始点权。

接下来 n1 行,每行两个数 x,y,表示第一棵树上节点 x 和节点 y 之间有一条边。

接下来 n1 行,每行两个数 x,y,表示第二棵树上节点 x 和节点 y 之间有一条边。

接下来 m 行,每行三个数 x,y,k,表示一次操作。

输出格式

输出 m 行,每行一个数,表示每次操作的答案。

样例输入 1

3 2
1 10 100
2 3
3 1
1 3
3 2
2 3 1000
1 1 10000

样例输出 1

2110
10001

样例输入 2

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

样例输出 2

15
21
10
13
17
26
18

数据范围

  • 对于所有数据满足 1n,m2×105
  • 0ai,k<264
  • 1x,yn
子任务编号 n,m 特殊性质 分值
1 3000 5
2 7×104 12
3 1.2×105 13
4 2×105 A 14
5 B 17
6 C 19
7 20
  • 特殊性质 A:保证第二棵树在所有 n 个节点的无根树中均匀随机生成。
  • 特殊性质 B:保证两棵树均为均匀随机生成的链。
  • 特殊性质 C:保证对于第一棵树,在以 1 为根的情况下,每个节点的父亲编号小于自己,且每个子树内节点编号连续,对于第二棵树的第 x 条边,连接节点 xx+1