UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3644. 陶陶的旅行计划

Statistics 下载数据

Description

  A国有N座城市,它们用正整数1…N进行编号。这些城市之间通过N-1条双向道路连接,使得任意两座城市间都有且仅有一条路径相连。定义两个城市间的距离为连接这两个城市路径上的边数。
  陶陶要在A国进行若干趟旅行,每次他会选择一个起点城市s和终点城市t,他从城市s开始,沿着s到亡的路径旅行,当他到达第i个城市时,可以选择坐火车到达与城市i距离不超过Ai的另一座城市,但这座城市必须要在S到t的路径上,你的任务是求出陶陶每趟旅
行最少需要坐多少次火车。
    除此之外,某些城市的火车车次中途会有改变,也就是说陶陶的每趟旅行之间可能夹杂了一些城市Ai值的改变。

Input

共N+M+2行。
第一行包含一个正整数Ⅳ,表示A国城市的数目。
第二行包含N个正整数,第i个正整数表示Ai (Ai≤20)。
 接下来有N-1行,每行包含两个正整数U,V(U,V≤N),表示城市u和V之间有一条双向道路相连。
  第N+2行包含一个正整数M,表示操作次数。
  下面M行,每行先给出一个字符,Q表示询问操作、C表禾修改操作。假如是询问操作,后面会有两个正整数s,t(s,t≤N,s≠t),分别表示起点城市和终点城市。假如是修改操作,后面会有两个正整数i,x(i≤N,x≤20),表示将Ai修改为x。

Output

包含若干行,对于每次询问输出对应的答案。

Sample Input


8
2 1 1 2 2 1 1 1
1 2
1 3
2 8
3 4
3 5
4 6
4 7
5
Q 5 8
Q 6 7
C 6 2
Q 6 7
Q 8 5

Sample Output

2
2
1
3

Hint

【样例说明】

  第一次询问的路线为5-->1-->8;

  第二次询问的路线为6-->4-->7;

  第三次询问的路线为6 -->7;

  第四次询问的路线为8-->2-->1-->5。


  对于100%的数据满足N≤100,000,M≤100,000。对于包含修改操作的数据,修改操作约占操作总数的三分之一。

Source