题目描述

炭治郎计划着去寻找蓝色彼岸花！已知有n个地点可能有蓝色彼岸花，炭治郎用1至n这个正整数对这些地点标号。n个地点通过n-1条双向道路相连，且任何两个不同的地点都能通过道路相连。

炭治郎对每个地点都有一个期望，这个期望值为一个整数，由于有些地点很危险，炭治郎对这些地点的期望可能是负的。在寻找蓝色彼岸花的途中，他会选择一个地点作为起点，并沿着存在的道路到其他地点寻找。炭治郎获得的期望就是他所经过的所有地点的期望值之和，因为地点与地点之间距离很远，炭治郎不会经过同一条路径两次。

由于蓝色彼岸花生长环境极为多变，炭治郎对于地点的期望值会随着时间发生变化，并且他也没有决定好应该从哪个地点开始寻找。因此他希望你能写一个程序帮他完成一个简单的任务：根据当前他对每个地点的期望值，计算从某个地点开始所能获得的最大的期望。

输入格式 输入的第一行包含一个正整数n。

第二行包含n-1个用空格隔开的整数，第i个整数表示炭治郎对i号景点的初始期望值。

接着有行，每行两个正整数a,b，表示从a号景点到b号景点有一条无向道路相连。

最后是一些指令，指令只会是以下三种格式：

1．Change u x 将u号景点的期望值修改为x。

2．Query u 询问从u号景点开始能获得的最大的期望。

3．Done 收到这个指令后，你的程序应该结束。

输出格式 对于每条Query指令，输出对应的最大快乐期望。