题目描述

一棵树有 $N$ 个点，编号为 $1 \sim N$。给出 $N-1$ 条边。节点有黑有白，每个节点都有权值。

有 $M$ 个操作。操作分为三种

$1$ $a$：表示将第 $a$ 个点的颜色置反（白变黑，黑变白）。

$0$ $a$：表示与编号为 $a$ 的点相连通的点（包括 $a$）中权值最大值。

$2$ $a$ $w$：表示将编号为 $a$ 的点的权值改为 $w \ (w \le 10^9)$。

输入格式

第 $1$ 行读入 $N$ $(1 \le N \le 10^6)$，表示有 $N$ 个点。

下来 $N-1$ 行输入 $X$，$Y$ $(1 \le X,Y \le N)$，表示 $X$ 与 $Y$ 之间有一条边。

下来一行 $N$ 个数，表示每个节点初始的颜色。$0$ 代表白色，$1$ 代表黑色

下来一行 $N$ 个数 $w_i \ (w_i \le 10^9)$，表示每个点的权值。

下来一行一个整数 $M$，$(1 \le M \le 10^5)$

下来 $M$ 行，表示 $M$ 个操作。

输出格式

每次 $0$ 操作时输出答案即可.

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

1
5