bzoj#P2836. 魔法树

魔法树

题目描述

Harry Potter 新学了一种魔法:可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树,来试验他的新法术。

这棵果树共有 NN 个节点,其中节点 00 是根节点,每个节点 uu 的父亲记为 faufa_u,保证有 fau<ufa_u<u。初始时,这棵果树上的果子都被 Dumbledore 用魔法清除掉了,所以这个果树的每个节点上都没有果子(即 00 个果子)。

不幸的是,Harry 的法术学得不到位,只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说,Harry 的魔法可以这样描述:Add u v d 。表示将点 uuvv 之间的路径上的所有节点的果子个数都加上 dd

接下来,为了方便检验 Harry 的魔法是否成功,你需要告诉他在释放魔法的过程中的一些有关果树的信息:Query u。表示当前果树中,以点 uu 为根的子树中,总共有多少个果子?

输入格式

第一行一个正整数 NN1N1000001 \le N \le 100000),表示果树的节点总数,节点以 0,1,,N10,1,\dots,N - 1 标号,00 一定代表根节点。

接下来 N1N - 1 行,每行两个整数 a,ba,b0a<b<N0 \le a < b < N),表示 aabb 的父亲。

接下来是一个正整数 QQ1Q1000001 \le Q \le 100000),表示共有 QQ 次操作。

后面跟着 QQ 行,每行是以下两种中的一种:

  1. Add u v d,表示将 uuvv 的路径上的所有节点的果子数加上 dd。保证 0u,v<N,0<d<1000000 \le u,v < N,0 < d < 100000
  2. Query u,表示询问以 uu 为根的子树中的总果子数,注意是包括 uu 本身的。

输出格式

对于所有的 Query 操作,依次输出询问的答案,每行一个。

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2
3
3
2

数据规模与约定

答案可能会超过 2322^{32},但不会超过 101510^{15}