Scout Gatherings

The scouting association has branches in $N$ cities, and the cities are connected by $N-1$ railway lines. Exactly one route runs from any city to any other city, so the cities and the lines form a tree.

Two cities are neighbors if a railway line connects them directly. The government subsidizes scouting, so one scout pays 1 kuna to ride one line section between two neighboring cities.

The association does only two things during the year:

• register a new member in a city
• hold a gathering in a city

Every member of the association travels to a gathering by train, and the association pays the fare. A member rides from their own city to the host city along the unique route, so one member's fare equals the number of line sections between the two cities. The first gathering of the year is always held in city $1$, and each later gathering is held in one of the neighbors of the city that hosted the previous gathering.

You know how many members each city has at the start of the year, and you know the registrations and the gatherings in the order they happened. Write a program that computes the total travel money spent on each gathering.

The first line contains the number of cities $N$. ($1 \le N \le 100{,}000$)

The second line contains the number of members in each city at the start of the year, from city $1$ onward. Every count is a non-negative integer smaller than $1{,}000$.

Each of the next $N-1$ lines contains one railway line as the numbers $A$ and $B$ of the two cities it connects. ($1 \le A \le N$, $1 \le B \le N$)

The next line contains the number of tasks $M$. ($1 \le M \le 300{,}000$)

Each of the next $M$ lines contains one task, in the order the tasks must be handled. A task is the character P or S followed by a city number $G$. ($1 \le G \le N$) P registers a new member in city $G$, and S holds a gathering in city $G$.

The first task is always a gathering in city $1$, and each later gathering is held in a city neighboring the city that hosted the previous gathering.

For each S task, print one integer on its own line, the total travel money spent on that gathering.

The total can exceed the range of a 32-bit integer, so use a 64-bit integer type.