스카우트 모임

스카우트 연맹은 전국 $N$개 도시에 지부를 두고 있고, 도시는 철도 노선 $N-1$개로 이어져 있다. 어떤 도시에서 다른 어떤 도시로 가는 길이 정확히 하나씩 있어서, 도시와 노선은 트리를 이룬다.

두 도시를 직접 잇는 노선이 있으면 두 도시는 이웃이다. 정부가 스카우트 활동을 지원해서, 이웃한 두 도시 사이의 노선 한 구간을 지나는 요금은 대원 한 명에 1쿠나다.

연맹이 한 해 동안 하는 일은 두 가지뿐이다.

• 어느 도시에 새 대원을 등록한다.
• 어느 도시에서 모임을 연다.

모임에는 연맹 대원 전원이 기차로 참석하고, 요금은 연맹이 낸다. 대원은 자기 도시에서 모임이 열리는 도시까지 유일한 경로로 이동하므로, 대원 한 명이 내는 요금은 두 도시 사이의 노선 구간 수와 같다. 그해 첫 모임은 항상 $1$번 도시에서 열리고, 그다음부터는 바로 앞 모임을 연 도시의 이웃 도시 중 하나에서 열린다.

한 해가 시작될 때 각 도시의 대원 수와, 새 대원 등록과 모임이 일어난 순서를 알고 있다. 모임마다 교통비로 쓴 총액을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$이 주어진다. ($1 \le N \le 100{,}000$)

둘째 줄에 한 해가 시작될 때 각 도시에 있는 대원 수가 $1$번 도시부터 순서대로 주어진다. 대원 수는 모두 $1{,}000$보다 작은 음이 아닌 정수다.

다음 $N-1$개 줄에 노선이 하나씩 주어진다. 각 줄에는 그 노선이 잇는 두 도시의 번호 $A$와 $B$가 주어진다. ($1 \le A \le N$, $1 \le B \le N$)

그다음 줄에 처리할 일의 수 $M$이 주어진다. ($1 \le M \le 300{,}000$)

다음 $M$개 줄에 처리할 일이 순서대로 주어진다. 각 줄은 문자 P 또는 S와 도시 번호 $G$로 이루어진다. ($1 \le G \le N$) P는 $G$번 도시에 새 대원을 등록하는 일이고, S는 $G$번 도시에서 모임을 여는 일이다.

첫 번째 일은 항상 $1$번 도시의 모임이고, 그다음 모임은 모두 바로 앞 모임을 연 도시의 이웃 도시에서 열린다.

S인 일마다 한 줄에 하나씩, 그 모임의 교통비 총액을 정수로 출력한다.

총액은 32비트 정수 범위를 넘을 수 있으니 64비트 정수 자료형을 쓰시오.