有 n 个节点,第 x 个节点有点权 ax,有两棵树分别独立地连接了这 n 个点,两棵树点权是共用的。
你需要进行 m 次操作,每次操作给定 x,y,k,进行以下两步:
- 将第一棵树上 x,y 之间最短路径上所有节点的点权增加 k;
- 求第二棵树上 x,y 之间最短路径上的点权和对 264 取模的结果。
输入格式
第一行两个数 n,m,表示节点数和操作数。
第二行 n 个数,第 x 个数表示 ax,即节点 x 的初始点权。
接下来 n−1 行,每行两个数 x,y,表示第一棵树上节点 x 和节点 y 之间有一条边。
接下来 n−1 行,每行两个数 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
数据范围
- 对于所有数据满足 1≤n,m≤2×105
- 0≤ai,k<264
- 1≤x,y≤n
子任务编号 | 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 条边,连接节点 x 和 x+1。