该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

数据已更新2019.7.17

【题意】

一开始给出一棵 $n$ 个点 $n-1$ 条无向边的树，每个点的权值 $w_i$。
有四种操作：

• 1 u v :在点 u 和点 v 之间建一条边。
• 2 u v :摧毁点 u 到点 v 之间的边。
• 3 w u v :将点 u 和点 v 之间路径上的点（包括u,v），权值增加 $w (0 \le w \le 3000)$。
• 4 u v :询问点 u 到点 v 之间路径上的点（包括u,v），权值最大值。

当操作违法时（询问一中u,v已经连通，询问二中u,v没有直接连边或不连通，三四中u,v不连通，一二操作u==v）不进行操作并输出-1。

【输入格式】

第一行一个正整数 $n \ (1 \le n \le 3 \times 10^5)$。
下来 $n-1$ 行，每行两个正整数 $u,v$，代表 $u$ 和 $v$ 之间有一条边。
下来 $n$ 个整数 $w_i (0 \le w_i \le 3000)$。
下一行一个正整数 $m \ (1 \le m \le 3 \times 10^5)$。 以下 $m$ 行，每行表示一个操作。

所有数据不爆int

【输出格式】

对每个4操作，输出点u到点v之间路径上的点（包括u,v），权值最大值。同时对于违法情况输出-1。

5
1 2
2 4
2 5
1 3
1 2 3 4 5
6
4 2 3
2 1 2
4 2 3
1 3 5
3 2 1 4
4 1 4

3
-1
7

【提示】

利用find_root判断违法。最值统计方式与翻转方式相仿,不过记得是让儿子的标记加上自己的标记！