bzoj#P2836. 魔法树
魔法树
题目描述
Harry Potter 新学了一种魔法:可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树,来试验他的新法术。
这棵果树共有 个节点,其中节点 是根节点,每个节点 的父亲记为 ,保证有 。初始时,这棵果树上的果子都被 Dumbledore 用魔法清除掉了,所以这个果树的每个节点上都没有果子(即 个果子)。
不幸的是,Harry 的法术学得不到位,只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说,Harry 的魔法可以这样描述:Add u v d
。表示将点 和 之间的路径上的所有节点的果子个数都加上 。
接下来,为了方便检验 Harry 的魔法是否成功,你需要告诉他在释放魔法的过程中的一些有关果树的信息:Query u
。表示当前果树中,以点 为根的子树中,总共有多少个果子?
输入格式
第一行一个正整数 (),表示果树的节点总数,节点以 标号, 一定代表根节点。
接下来 行,每行两个整数 (),表示 是 的父亲。
接下来是一个正整数 (),表示共有 次操作。
后面跟着 行,每行是以下两种中的一种:
Add u v d
,表示将 到 的路径上的所有节点的果子数加上 。保证 。Query u
,表示询问以 为根的子树中的总果子数,注意是包括 本身的。
输出格式
对于所有的 Query
操作,依次输出询问的答案,每行一个。
4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2
3
3
2
数据规模与约定
答案可能会超过 ,但不会超过 。