/ Vijos / 题库 /

小h的妹子树二

小h的妹子树二

背景

小h同学的妹子实在是太多辣,多的他又种下了一颗妹子树。

描述

树上有n个妹子,两两之间有且仅有一条路径。

小h每次想泡两个妹子,但是妹子是一种奇怪的生物(雾),小h无论想泡哪一对妹子,都得为她们路径上的所有妹子支付软妹币(P.S.泡一个不就好了)。

这次我们的妹子树形态不会变了,但是她们需要的软妹币会变化。

小h很苦恼,他需要知道每一次泡妹子需要多少预算,他请求了小y,小y当然会辣,他想考考你。

支持两种操作:
Q u v 询问泡u和v的价值
C u v改变u的权值为v

格式

输入格式

输入文件第一行是一个整数n,表示n个妹子,从1开始编号。

输入文件第二行是n个正整数Vi,表示每个妹子的初始所需软妹币。

接下来n-1行,每行两个整数u和v,表示u和v有一条边。

然后是一个整数m,一共m此操作

接下来m上格式如上。

输出格式

对于每一次询问操作,你需要输出一个整数,表示所需的软妹币,每行一个答案。

样例1

样例输入1

3
1 2 3
1 2
2 3
5
Q 1 2
Q 1 3
C 2 3
C 3 5
Q 1 3

样例输出1

3
6
9

限制

对于前20%的数据,满足1<=n<=300,1<=m<=500
对于前60%的数据,满足1<=n<=3000,1<=m<=5000
对于20%的数据,是一条链
对于前50%的数据,保证是完全随机
对于前80%的数据,满足1<=n<=30000,1<=m<=50000
对于100%的数据,满足1<=n<=100000,1<=m<=200000,1<=Vi<=1000

来源

感谢 yql 提供。

信息

ID
1986
难度
7
分类
小h的妹子树 点击显示
标签
(无)
递交数
150
已通过
33
通过率
22%
上传者

相关

在下列训练计划中:

RP++分类题库