/ Vijos / 题库 /

小h的妹子树一

小h的妹子树一

背景

小h经过仔细的筛选,终于选出了最好的妹子树种子。他种下了这颗种子,长出了一颗茁壮的妹子树,终于到了收获的季节。

描述

由于某些奇怪的原因,小h每次需要同时找到两个妹子(QAQ),但是由于妹子是一种很奇怪的生物,小h想要泡两个妹子,就要把连接她们的路径上的所有妹子全部泡到,当然泡妹子是需要软妹币的啦,小h可是很穷的(雾)。
由于小h疏于管理他的妹子树,这个妹子树长成了一片妹子森林(QAQ),但妹子们是会感到孤独的,有时候两个妹子会成为新的朋友啦。

小h很苦恼,他不知道他应该泡哪对妹子,他需要提前知道泡她们的代价。于是他请小y帮忙,小y当然会辣,他想考考你。

支持两种操作:
Q u v:询问泡u和v的最小代价,保证u和v联通
L u v:连接u和v,保证u和v之前不联通。

我会使用一些方法强制在线。
每次你读入的一对u和v,实际应当是u^lastans,v^lastans,lastans是上一次的答案,默认一开始lastans为0,其中L u v操作不会修改lastans的值。

格式

输入格式

第一行是一个正整数n,表示一共有n个妹子,从1开始编号。
下面一行n个正整数Vi,Vi表示泡第i个妹子的代价。
然后是n行,每行给出两个1到n的数u和v,表示u和v之间有一条边,若u为0,则代表v是根节点。
接下来一个正整数m,表示共m次操作。
以下m行每行一个操作,格式见上。

输出格式

对于每一个询问操作输出一个数,表示同时泡的最小代价,每行一个数。

样例1

样例输入1

8
406 706 450 451 715 126 120 530 
0 1
0 2
6 3
1 4
8 5
4 6
0 7
1 8
8
Q 4 1
L 861 859
Q 859 860
L 2812 2815
Q 2813 2809
Q 1652 1653
Q 698 696
Q 1436 1435

样例输出1

857
2808
1651
697
1433
2808

限制

对于30%的数据,保证1<=n<=3000,1<=m<=5000

对于70%的数据,保证1<=n<=30000,1<=m<=50000

对于90%的数据,保证1<=n<=100000,1<=m<=100000

对于100%的数据,保证:1<=n<=100000,1<=m<=200000,1<=Vi<=1000

来源

感谢 yql 提供。

信息

ID
1985
难度
6
分类
小h的妹子树 点击显示
标签
(无)
递交数
70
已通过
21
通过率
30%
上传者

相关

在下列训练计划中:

RP++分类题库