Migrated from Lutece 2537 芜湖塔台请求起飞

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

金牌讲师马老师用直播赚到的钱买了一架私人飞机。因为他最喜欢在芜湖吃芜湖名菜红皮鸭子，所以把飞机停在了芜湖机场。芜湖机场的工作人员每天都跟着马老师吃得很饱，以至于没有精力打理机场，所以机场跑道上不知不觉中长出了一棵长满了红皮鸭子的树。

现在，马老师需要起飞会见各地朋友，但是被这棵树挡住了去路。芜湖塔台在无线电通讯里告诉他，如果他想要起飞，就必须和这棵树进行交流，让这棵树挪一下位置。马老师转眼看向了你，说：「因为你不会，所以你才会，我相信天赋异禀的你可以完成这件事！」

你平时也跟着马老师一起吃饭，所以不好推脱他的请求，正在这时，这棵树竟说了一句「歪比歪比，歪比巴卜」，马老师听后会心一笑，告诉你：

这棵树有 $n$ 个红皮鸭子悬挂点，每个悬挂点上都挂了若干只红皮鸭子（数量为负数时表示点上的鸭子被提前预定了），有些悬挂点之间存在一条无向路。树只有在你完成 $Q$ 个操作后才会让路，操作类型包括：

1. 你拿走或预定某个红皮鸭子悬挂点上的一些红皮鸭子，或者再挂一些上去，使得这个点有特定只红皮鸭子；
2. 询问某两个红皮鸭子悬挂点的路径上一共有多少只红皮鸭子；
3. 询问某两个红皮鸭子悬挂点的路径上挂的红皮鸭子最多的节点挂了多少只。

需要注意的是，后两种询问所说的路径均包含起止点。

Input

第一行有 $1$ 个整数 $n$，表示树上红皮鸭子悬挂点的数目，编号从 $1$ 到 $n$ ；

然后有 $n - 1$ 行，每行有 $2$ 个整数 $a$、$b$，表示有一条无向路连接编号为 $a$、$b$ 的两个悬挂点。

然后有 $n$ 个整数 $w_i$，表示编号为 $i$ 的悬挂点上有 $w_i$ 只红皮鸭子。

然后有 $1$ 个整数 $Q$，表示红皮鸭子树会给你的操作数。

接下来 $Q$ 行，每行的格式如下：

• 首先给一个范围在 $[1, 3]$ 的整数 $t$，表示需要你进行的操作类型，类型和题目描述对应。
• 若 $t$ 为 $1$，在同一行内会再给两个整数 $u$、$x$，表示现在编号为 $u$ 的悬挂点上有 $x$ 只红皮鸭子。
• 若 $t$ 为 $2$ 或 $3$，在同一行内会再给两个整数 $u$、$v$，表示题目中两个红皮鸭子悬挂点的编号。

Output

在 $Q$ 次操作中，对于 $t$ 为 $2$ 或 $3$ 的操作，输出一行一个整数表示题目描述所求数据。

Samples

4
4 1
1 2
2 3
5 2 7 9
12
3 3 4
3 3 3
3 3 2
3 2 3
2 3 4
2 2 1
1 1 5
3 3 4
1 3 6
3 3 4
3 2 4
2 3 4

9
7
7
7
23
7
9
9
9
22

Constraints

$1 \le n \le 3\times 10^4$，$0 \le Q \le 2\times 10^5$，任意时刻 $\sum_{i=1}^n w_i$ 和 $w_i$ 均保持在 int 类型范围内。

保证所给的无向路能够组成一棵树。

Resources

2021 UESTC ICPC Training for Data Structures