U595295 膜铮题

 被 LCT 草了。当然用 LCT 就没意思了，想想更膜铮的做法吧！

现有一棵 $n$ 个节点的树，有以下 $3$ 种操作： - 将点 $u,v$ 的路径上所有点的点权增加 $k$； - 求点 $u,v$ 的路径上的点权和； - 增加一个叶子节点。 我们会用一种方法强制你在线。

第一行 $3$ 个数 $n,m,c$，表示初始时树的节点数 $n$ 和总共的操作数 $m$，$c$ 的含义将在下文给出。 第二行 $n$ 个数，第 $i$ 个数 $a_i$ 表示点 $i$ 的点权为 $a_i$。 接下来 $n-1$ 行，每行两个数 $u,v$，表示初始时树上的一条边。 接下来 $m$ 行，每行第一个数 $op$： - 若 $op=1$，接下来 $3$ 个数 $u',v',k$，表示将点 $u,v$ 路径上所有点权加 $k$； - 若 $op=2$，接下来 $2$ 个数 $fa',x$，表示新加一个点权为 $x$，父节点为 $fa$ 的**叶子节点**，编号为加入该节点之前的节点数量加 $1$； - 若 $op=3$，接下来 $2$ 个数 $u',v'$，表示查询点 $u,v$ 的路径上的点权和。 对于带有 $'$ 的变量，你需要按照以下方式解密：设其为 $x'$，当前节点数为 $tot$（不包含**这次操作**新加的节点。比如，当前共有 $5$ 个节点，则无论哪种操作当前 $tot$ 都等于 $5$），则 $x=(x'-1+c\times \text{lastans})\bmod tot+1$。$\text{lastans}$ 为上一次查询操作的答案，初始为 $0$。

对于每个查询操作，输出一行一个数。

**可能需要极大程度的的常数优化。** 保证输入的所有数是整数。 本题采用捆绑测试，也就是说，对于一个子任务，你必须通过其中所有的测试点才能得到分数。 | 子任务编号 | 数据范围与约定 | 分数 | |:-:|:-:|:-:| | 1 | $n,m\le 10$ | 5 | | 2 | $n,m\le 2000$ | 15 | | 3 | $c=0$ | 20 | | 4 | 无特殊限制 | 60 | 对于所有数据： - $1\le n,m\le 2\times 10^5$； - $ |a_i|,|k|,|x|\le 10^9$； - $c\in\{0,1\}$； - $op\in\{1,2,3\}$； - $u',v',fa'$ 为小于等于当前节点数量的正整数。 [题解](https://www.luogu.com.cn/paste/ccjfzihh)