현식이는 N개의 도시가 있는 나라에 살고 있습니다. 이 N개의 도시는 N-1개의 길로 연결되어 있으며 트리 구조를 이룹니다.

이 N개의 도시에서는 같은 물건을 파는데, 현식이의 나라는 공화국이기 때문에 각 도시에서 물가가 같지 않을 수 있습니다. 현식이는 여행을 좋아하기 때문에 도시들을 여행하고 싶어합니다.

하지만 현식이는 여행을 좋아하는 것보다도 돈을 더 좋아하기 때문에 여행을 하는 동안 돈을 벌고자 합니다. 현식이가 돈을 버는 방법은 단순합니다. 가는 길에 있는 도시에서 물건 하나를 사서, 그 후 방문하는 도시에서 그 물건을 팝니다. 이윤은 물건을 판 가격에서 산 가격을 뺌으로서 정의됩니다.

현식이는 도시 A에서 B로 가는 동안 얻을 수 있는 최대 이윤을 알고 싶어 합니다.

현식이는 이를 프로그램으로 짜 보려 했으나, 도시들의 물가가 시시각각 변한다는 사실을 알고는 귀찮아져 당신에게 이것을 부탁했습니다. 이런 상황에 처한 현식이를 도와주세요!

현식이는 바쁜 남자이기 때문에 이윤을 위해 경로를 바꾸거나 길을 되돌아가는 일은 없습니다. 또한 물건을 사고 파는 데는 오래 걸리기 때문에 가는 길에 두 번 이상 물건을 사거나 파는 일은 없습니다.

물건을 산 도시에서 되팔 수는 있으나 이 때 이윤은 0입니다. 임의의 도시에서 물건을 사는 가격과 파는 가격은 서로 같고, 꼭 물건을 산 후에 되팔아야 합니다. 임의의 도시에서 물건을 사는 가격과 파는 가격은 같고, 꼭 물건을 산 후에 되팔아야 합니다(중요!).

질문의 종류는 두 가지가 있는데, 다음과 같습니다.

1. Q a b : 도시 a에서 b로 가는 동안 얻을 수 있는 최대 이윤을 출력합니다.
2. C a t_i : 도시 a의 물가를 t_i로 바꿉니다.

입력

• 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000)과 질의의 수 Q(1 ≤ Q ≤ 100,000)가 주어집니다. 도시들은 1부터 N까지 번호가 매겨져 있습니다.
• 그 다음 (N-1)줄에는 도시를 잇는 길들이 주어집니다. a b는 도시 a와 도시 b를 잇는 길이 있다는 것을 의미합니다.
• 그 다음 N줄에는 각 도시들의 초기 물가 x_i가 주어집니다.(1≤xi≤10^8)
• 그 다음 Q줄에는 질의가 주어집니다.

출력

입출력 예

입력 예1

3 1
1 2
2 3
3
1
2
Q 3 1

출력 예1

2

입력 예2

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

출력 예2

3
1
0
2
3

입출력 보충

-전체의 20%에 해당하는 데이터는 N,Q≤100입니다.
-전체의 40%에 해당하는 데이터는 N,Q≤3,000입니다.
-나머지 60% 중 20%에 해당하는 데이터는 N,Q≤100,000이며 도시는 서로 직선을 이룹니다. 즉, i번째 간선은 i와 i+1번째 도시를 연결합니다.
-나머지 40%에 해당하는 데이터는 N,Q≤100,000이며 추가 제약은 없습니다.

출처: zlzmsrhak 
참조: http://www.poj.org/problem?id=3728