#PQJ1813x9492. QOJ 1813_9492
QOJ 1813_9492
标题: 树上简单求和 - Problem - QOJ.ac
#9492. 树上简单求和
The problem was used in the following contests:
有 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。