P12511 [集训队互测 2024] 树上简单求和

有 $n$ 个节点，第 $x$ 个节点有点权 $a_x$，有两棵树分别独立地连接了这 $n$ 个点，两棵树点权是共用的。 你需要进行 $m$ 次操作，每次操作给定 $x,y,k$，进行以下两步： 1. 将第一棵树上 $x,y$ 之间最短路径上所有节点的点权增加 $k$； 2. 求第二棵树上 $x,y$ 之间最短路径上的点权和对 $2^{64}$ 取模的结果。

第一行两个数 $n,m$，表示节点数和操作数。 第二行 $n$ 个数，第 $x$ 个数表示 $a_x$，即节点 $x$ 的初始点权。 接下来 $n - 1$ 行，每行两个数 $x,y$，表示第一棵树上节点 $x$ 和节点 $y$ 之间有一条边。 接下来 $n - 1$ 行，每行两个数 $x,y$，表示第二棵树上节点 $x$ 和节点 $y$ 之间有一条边。 接下来 $m$ 行，每行三个数 $x,y,k$，表示一次操作。

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

- 对于所有数据满足 $1 \leq n,m \leq 2 \times 10^5$ - $0 \leq a_i,k < 2^{64}$ - $1 \leq x,y \leq n$ | 子任务编号 | $n,m \leq$ | 特殊性质 | 分值 | | --- | --- | --- | --- | | 1 | $3000$ | 无 | 5 | | 2 | $7 \times 10^4$ | 无 | 12 | | 3 | $1.2 \times 10^5$ | 无 | 13 | | 4 | $2 \times 10^5$ | A | 14 | | 5 | $2 \times 10^5$ | B | 17 | | 6 | $2 \times 10^5$ | C | 19 | | 7 | $2 \times 10^5$ | 无 | 20 | - 特殊性质 A：保证第二棵树在所有 $n$ 个节点的无根树中均匀随机生成。 - 特殊性质 B：保证两棵树均为均匀随机生成的链。 - 特殊性质 C：保证对于第一棵树，在以 $1$ 为根的情况下，每个节点的父亲编号小于自己，且每个子树内节点编号连续，对于第二棵树的第 $x$ 条边，连接节点 $x$ 和 $x + 1$。