9272 - 包裹
现在我国货物运输以及包裹运输的主要方式仍然是依靠公路运输，包裹运输主要由快递公司统一运送到某一特定的地方，在根据地址或区域分别派送到包裹的指定地点。 京东作为目前的电商巨头之一，在全国很多地方都建立了货运中心，京东每天的订单量都是非常多，同时包裹需要发送到全国各地，这些包裹均会按照省份先运送到各省的物流中心，在进行分拣发送到各个市、区/县……，这样的运输网络我们可以看成一棵树，货运中心就为根节点，各省物流中就为根节点的子结点，以此类推。 昆明就有一个京东的货运仓库，假设现在京东收到了一批订单，这批订单需要发送到n个地方，编号从1到n，到达每个站点的包裹有w个，站点和站点之间只存在一条路线；在运输过程中可能会出现，用户退货或者站点新收包裹需要寄送的情况，对于这两种情况京东会在某个运输站点将退货包裹挑拣出来重新返回仓库，将需要寄送包裹加入运输的包裹中，则在此站点的包裹数量将会减少或增加；现在为了减少各站点的工作量，有如下几个操作： （1）CHANGE u t ：站点u的包裹数量为t。 （2）QMAX u v ：询问从站点u到站点v的包裹那个站点的包裹数量最多。 （3）QSUM u v ：询问从站点u到站点v的包裹总和。 注意：从点到点的路径上的结点包括和本身。
共12次操作： 第1次查询3到4路径上的最大值，具体路径3-2-1-4为，路径结点中权值最大为1号结点，权值为4，故输出4。 第2、3、4次查询与第1次类似。 第5次查询3到4路径权值之和，具体路径为3-2-1-4，结点权值之和为1+2+4+3=10，故输出。 第6次查询与第5次类似。 第7次为改变1号结点的权值为5。 ……
输入
第一行1为个正整数n，表示结点的个数。 接下来的n-1行，每行2个整数x和y，表示站点x和站点y之间有一条路线。 接下来的n个整数，第in个正整数w_i，表示站点i的包裹数量。 接下来的1行表示有q次操作。 接下来的q行，每行一个操作，以CHANGE u t或QMAX u v或QSUM u v的形式给出。
输出
对于每个QMAX或QSUM的操作，每行一个整数表示要求输出的结果。
样例
输入
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
提示
对于 100%的数据，保证
2 \leq n \leq 3* \gdef\foo#1{#1^4} \foo{10}
0 \leq q \leq 2* \gdef\foo#1{#1^5} \foo{10}
-3 \ast \gdef\foo#1{#1^4} \foo{10} \leq w_i \leq 3 \ast \gdef\foo#1{#1^4} \foo{10}
来源
云南编程挑战赛