귀찮은 사업가2

프로그램 명: GoDjail

제한시간: 2 초

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

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

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

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

현식이는 지난번에 여러분이 짠 코드를 이용하여 많은 돈을 벌었습니다. 이를 마음에 들지 않아 했던 GoDjail(갓재일)은 현식이가 많은 이윤을 얻지 못하게 하도록 훼방을 놓으려 합니다. GoDjail의 계획대로 되지 않도록 현식이를 도와 주세요!

GoDjail은 현식이를 괴롭히기 위해 다음과 같은 두 가지 방법을 사용합니다.

J a b C : GoDjail이 도시 a에서 도시 b로 이동합니다. GoDjail이 이동 중 만나는 모든 도시의 물가는 GoDjail의 이름값 때문에 물가가 C( 0 ≤ C ≤ 10,000) 만큼 오릅니다. (도시 a와 도시 b의 물가도 같이 오릅니다)
K a b C : GoDjail이 도시 a에서 도시 b로 이동하며 만나는 모든 도시의 물가를 C( 1 ≤ C ≤ 10^9)로 바꾸어 버립니다. 마찬가지로 도시 a와 도시 b의 물가도 같이 바뀝니다.

당신이 답해야 하는 질의는 다음과 같습니다.

Q a b : 도시 a에서 b로 가는 동안 얻을 수 있는 최대 이윤을 출력합니다.

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

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

입력

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

출력

질의 중 Q a b에 해당되는 답을 한 줄에 하나씩 출력해 주세요.

입출력 예

입력 예1

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

출력 예1

2

입력 예2

4 8
1 2
2 3
2 4
5
2
4
1
Q 3 1
Q 1 3
J 2 2 2
Q 3 1
K 1 3 3
Q 3 1
J 1 4 3
Q 3 1

출력 예2

3
2
1
0
3

입출력 보충

예 1번에서, 현식이는 2->3->1의 경로를 거쳐서 가게 됩니다. 2번 도시에서 물건을 1에 사서 1번 도시에서 물건을 3에 되팔면 총 2의 이윤을 얻고, 이 값이 최대입니다.

예 2번
물가는 각각 5,2,4,1
Q 3 1 : 현식이는 3->2->1의 경로를 거쳐서 가게 되고, 5 - 2 = 3이 답입니다.
Q 1 3 : 현식이는 1->2->3의 경로를 거쳐서 가게 되고, 4 - 2 = 2가 답입니다.
J 2 2 2 : GoDjail이 2번 도시의 물가를 2 올렸고, 네 도시의 물가는 5,4,4,1이 됩니다.
Q 3 1 : 현식이는 3->2->1의 경로를 거쳐서 가게 되고, 5 - 4 = 1이 답입니다.
K 1 3 3 : GoDjail은 1->2->3의 경로를 거쳐 모든 도시의 물가를 3으로 바꾸었고, 네 도시의 물가는 3,3,3,1이 됩니다.
Q 3 1 : 현식이는 3->2->1의 경로를 거쳐서 가게 되고, 3 - 3 = 0이 답입니다.
J 1 4 3 : GoDjail은 1->2->4의 경로를 거쳐 모든 도시의 물가를 3씩 올렸고, 네 도시의 물가는 6,6,3,4이 됩니다.
Q 3 1 : 현식이는 3->2->1의 경로를 거쳐서 가게 되고, 6 - 3 = 3가 답입니다.

전체의 20%에 해당하는 데이터는 N,Q≤100입니다.

-전체의 40%에 해당하는 데이터는 N,Q≤3,000입니다.

-나머지 60% 중 8%에 해당하는 데이터는 N,Q≤100,000이며 GoDjail이 현식이를 방해하지 않습니다. 즉, Q a b 꼴의 질의만 입력됩니다.

-나머지 52% 중 20%에 해당하는 데이터는 N,Q≤100,000이며 도시는 서로 직선을 이룹니다. 즉, i ( 1≤i≤N-1 )번째 간선은 i와 i+1번째 도시를 연결합니다.

-나머지 32%에 해당하는 데이터는 N,Q≤100,000이며 추가 제약은 없습니다.

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

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]