P7671 [GDOI2016] 疯狂动物城

原题空间限制 512MB。 --- Nick 是只在动物城以坑蒙拐骗为生的狐狸，儿时受到偏见的伤害，放弃了自己的理想。他被兔子 Judy 设下圈套，被迫与她合作查案，而卷入意想不到的阴谋，历尽艰险后成为搭档。他们识破了绵羊副市长 Bellwether 的计划，发现是 Bellwether 陷害食肉动物，用毒药让食肉动物发狂。Bellwether 被抓到了监狱里面， Nick 和 Judy 过上了一段平静的日子。 然而，故事并没有这样结束，之前在车管所帮他们查车牌号的憨厚的树懒 Flash，才是陷害食肉动物事件的幕后主使。Flash 批量制作了大量让食肉动物发狂的药剂，投放到了食肉动物群中。现在，大量的食肉动物被感染，动物城陷入了一片混乱。警察局的牛局长 Bogo 找到了 Nick，希望他能帮忙。幸运的是，动物城联邦安全局非常有先见之明，他们在每个州都秘密放置了一台机器，机器能生产能量石，这些能量石能让食肉动物恢复正常。现在 Nick 和 Judy 需要去启动这些机器。

**提示：我们在文末提供了一份形式化题意。** 动物城是一个有 $N$ 个州的联邦，该联邦是一个树的形状，即 $N$ 个州共有 $N-1$ 条双向道路连接它们，且 $N$ 个州是相互连通的。$N$ 个州的编号依次为 $1,2,3,\dots,N$。每个州都有且仅有一台机器。一台机器启动后的下一个时刻，就会开始生产能量石，每个单位时间生产一个。能量石从被生产的时刻开始即生效，每一个单位时间能救一定数量的食肉动物。每个州的解毒机器制造出的能量石的品种可能是不同，第 $i$ 个州的机器生产的能量石每个单位时间能救 $a_i$ 只食肉动物。 Nick 和 Judy 剩下的时间不多了，他们决定分工合作。 Nick 从 $X$ 州出发，目的地为 $Y$ 州，路径为 $X$ 到 $Y$ 的最短路径。 Nick 从 $X$ 州出发的时刻为 $0$，每隔一个单位时间移动一个州。每到一个州，Nick 就会启动这个州的机器。 Nick 想知道他从 $X$ 州出发到达 $Y$ 州的这段时间里，一共有多少食肉动物被拯救。Nick 在纠结他的路线选择，因此，他会给你若干的询问，希望比他更聪明的你能帮助他。 在他给你询问的过程中，动物城的局势也在发生着一些变化。动物城联邦安全局可以执行一个修改操作 $X,Y,\Delta$，会对 $X$ 州到 $Y$ 州的最短路径上的州（包括 $X,Y$ 州）的机器进行升级，这样，这些机器生产出来的能量石，每个单位时间能救的食肉动物的数量会增加 $\Delta$。 树懒 Flash 当然也不会坐以待毙，他有一台监控仪，会监控每个州的机器的情况，每当有机器被升级，监控仪就会保存下当前所有州的机器的属性 $a_i$。Flash 可以用一种神秘的武器执行一个读取操作 $X$，把当前各个州的机器恢复到第 $X$ 次保存的状态（$X=0$ 表示未进行过升级时的初始状态）。注意，只有修改操作执行的时后会进行保存。 现在，依次给出 $M$ 个操作，若该操作为一个询问，请你输出 Nick 在当前局面下，他从 $X$ 州出发到达 $Y$ 州的这段时间里，一共有多少食肉动物被拯救，由于这个答案可能很大，你只需要输出答案模 $20160501$ 后的值。请注意，$M$ 个操作都是被加密过的。 **** **形式化题意**： 给你一棵 $N$ 个点的树，接下来有三种操作共 $M$ 次： - `1 x y w`，表示将 $x$ 到 $y$ 的路径上的所有点的点权加上 $w$。 - `2 x y`，表示一次询问。记 $x$ 到 $y$ 的路径上的点集为 $S(x,y)$，点 $p,q$ 之间的路径长度为 $\text{dis}(p,q)$，求出 $\sum_{i\in S(x,y)}\sum_{j\le \text{dis}(i,y)}a_i\cdot j$ 的值。将答案对 $20160501$ 取模。 - `3 x`，表示将这棵树的所有点权恢复到第 $x$ 次 `1` 操作之后的状态。 强制在线。

第一行 $2$ 个整数 $N,M$ 表示节点个数和操作次数。 接下来 $N-1$ 每行 $2$ 个整数 $u,v$ 表示了这棵树中 $u$ 和 $v$ 这 $2$ 个州间有边相连。 接下来一行 $N$ 个整数, 表示这 $N$ 个州的机器制造的能量 $a_i$ 的初始值。 接下来 $M$ 行每行先有一个数字表示了操作的类型： - 类型 1，代表一个修改操作，接下来有 $3$ 个整数 $X',Y',\Delta$。 - 类型 2，代表一个询问操作，接下来有 $2$ 个整数 $X',Y'$。 - 类型 3，代表一次读取操作，接下来 $1$ 个整数 $X'$。 其中 $X',Y'$ 表示加密后的数字。正确的 $X=X' \text{xor lastans} ,Y=Y' \text{xor lastans}$。其中 $\text{lastans}$ 为上次 `2` 操作取模后的答案，如果之前没有 `2` 操作过那么其值等于 $0$。

对于每个操作 `2`，输出一行，每行一个数，为所询问的答案模 $20160501$ 后的值。

对于所有数据，保证 $1\le n,m\le 10^5$，$1\le a_i,\Delta\le 10^5$，$1\le x,y\le n$。 对于其中 $20\%$ 的数据，保证 $n,m\le 2000$。 对于另外 $20\%$ 的数据，保证树为一条链，且不含有操作 `3`。 对于另外 $40\%$ 的数据，保证树为一条链。