5518: 包裹（package）

现在我国货物运输以及包裹运输的主要方式仍然是依靠公路运输，包裹运输主要由快递公司统一运送到某一特定的地方，在根据地址或区域分别派送到包裹的指定地点。

京东作为目前的电商巨头之一，在全国很多地方都建立了货运中心，京东每天的订单量都是非常多，同时包裹需要发送到全国各地，这些包裹均会按照省份先运送到各省的物流中心，在进行分拣发送到各个市、区/县……，这样的运输网络我们可以看成一棵树，货运中心就为根节点，各省物流中就为根节点的子结点，以此类推。

昆明就有一个京东的货运仓库，假设现在京东收到了一批订单，这批订单需要发送到 n 个地方，编号从 1 到 n，到达每个站点的包裹有 w 个，站点和站点之间只存在一条路线；在运输过程中可能会出现，用户退货或者站点新收包裹需要寄送的情况，对于这两种情况京东会在某个运输站点将退货包裹挑拣出来重新返回仓库，将需要寄送包裹加入运输的包裹中，则在此站点的包裹数量将会减少或增加；现在为了减少各站点的工作量，有如下几个操作：

（1）CHANGE u t：站点 u 的包裹数量为 t。

（2）QMAX u v：询问从站点 u 到站点 v 的包裹那个站点的包裹数量最多。

（3）QSUM u v：询问从站点 u 到站点 v 的包裹总和。

注意：从点 u 到点 v 的路径上的结点包括 u 和 v 本身。

第一行为一个整数 n，表示结点的个数。

接下来的 n−1 行，每行 2 个整数 x 和 y，表示站点 x 和站点 y 之间有一条路线。

接下来的 n 个整数，第 i 个整数 w_i​，表示站点 i 的包裹数量。

接下来的 1 行表示有 q 次操作。

接下来的 q 行，每行一个操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v 的形式给出。

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

4
1
2
2
10
6
5
6
5
16