#PQJ1813x9492. QOJ 1813_9492

    ID: 2709 传统题 6000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测最短路径线段树

QOJ 1813_9492

标题: 树上简单求和 - Problem - QOJ.ac

#9492. 树上简单求和

Statistics

The problem was used in the following contests:

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

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

  1. 将第一棵树上 x,y 之间最短路径上所有节点的点权增加 k;
  2. 求第二棵树上 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。