说明

时间限制：2 Sec 内存限制：256 MB 输入文件：three.in 输出文件：three.out

小红所居住的小镇上有一棵神木，树上住着树精灵。如果在树的某个顶点放置“三木之物”，附近的精灵就会聚集到这个顶点。

给定一棵无向树，共有 $N$ 个顶点，编号从 $0$ 到 $N-1$，有 $N-1$ 条边。第 $i$（$0 \le i < N-1$）条边连接顶点 $u_i$ 和 $v_i$。顶点 $i$（$0 \le i \le N-1$）初始有 $A_i$ 只精灵。

精灵只会停留在顶点上，习性如下：

如果在距离自身所在顶点不超过 $2$ 的顶点放置了“三木之物”，精灵就会移动到放置该物品的顶点。

移动完成后，精灵停留在目标顶点。

两点之间的距离定义为两点路径上包含的边的条数。

按顺序处理 $Q$ 次询问：

- 给定 $x$：在顶点 $x$ 放置“三木之物”。之后求出此时顶点 $x$ 上精灵的总数。

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $u_i,v_i$。

接下来一行 $N$ 个整数 $A_0,A_1,\dots,A_{N-1}$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $x_i$。

输出格式

一共输出 $Q$ 行，第 $i$ 行输出第 $i$ 次询问对应的答案。

样例

样例 1

10
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
0 1 2 3 4 5 6 7 8 9
3
1
4
0

34
34
45

样例说明：

与顶点 $1$ 距离不超过2的顶点有 $0,1,2,3,4,7,8,9$。所以顶点 $1$ 汇集精灵总数 $0+1+2+3+4+7+8+9=34$。

最后一次询问顶点 $0$，树上全部精灵都会汇集到顶点 $0$。

数据范围

对于 20% 的数据，$N \le 100$，$Q \le 100$。

对于 100% 的数据，$2 \le N \le 10^5$，$0 \le A_i \le 10^5$，$1 \le Q \le 10^5$，$0 \le x_i \lt N$。

对于 100% 的数据，$0 \le u_i,v_i \lt N,\ u_i \neq v_i$，保证边不重复。