问题2631--B

2631: B

时间限制: 1 Sec  内存限制: 128 MB
提交: 33  解决: 9
[状态] [讨论版] [提交] [命题人:]
题目描述
小p很早就听说,在古老的埃及,想要从斯芬克斯守护的地方经过,需要回答对它的一个问题。小p自命不凡,来到了斯芬克斯面前。斯芬克斯每天都望向远处(很远很远)的森林,看着一棵树,树上时不时会有一些小鸟落下,它每天的乐趣就是,当树上的小鸟的数量变化的时候,统计现在树上从一个树叶到另一个树叶上有多少个小鸟,它费尽心思没有搞懂,恰好小p来了,于是它将问题丢给小p,并说到:“我每天望向对面的森林,每天凌晨的时候,树上没有一只小鸟,每当有小鸟来的时候,我就记录 2 x y z,表示这个时候,从x号树叶到y号树叶的路径上每个树叶都多了z只小鸟,每过一段时间,我还会记录 1 x y,表示我现在想知道此时树上x号叶子到y号叶子的路径上小鸟的总数,那么剩下的就交给你了,你要勇于尝试,要么尝试解答,要么尝试丧命。”
输入

第一行一个数字n,表示树上点的个数(1 <= n <= 100000)

第2~n行,每行两个数字x y表示树上一条边,其中x是y 的父节点。

第n + 1行,一个数字q,表示斯芬克斯记录的总数,每个记录的形式如下:

1 x y

2 x y z

含义如题目所示。

输出

对每一个如下形式的记录:

1 x y
输出一行,表示查询的结果

样例输入 Copy
3
1 2
2 3
2
2 1 2 1
1 1 3
样例输出 Copy
2
来源/分类