陶陶的旅行计划

时间限制:30s      空间限制:256MB

题目描述

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


输入格式

共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。


输出格式

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


样例输入

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                       


样例输出

2
2
1
3

提示

【样例说明】
  第一次询问的路线为5-->1-->8;
  第二次询问的路线为6-->4-->7;
  第三次询问的路线为6 -->7;
  第四次询问的路线为8-->2-->1-->5。

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


题目来源

没有写明来源