|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
Given a tree with $n$ vertices numbered from $1$ to $n$. Each vertex $i$ has an initial value $W_i$. You need to perform two types of queries:
- add(v, x): Increase the value for all neighbors of v with x. It is guaranteed that $1 \leq v \leq n$ and $1 \leq x \leq 1000$.
- get(v): Print the value of vertex v ($1 \le v \le n$).
Input
The first line of input contains the number of vertices ($1 \leq n \leq 10^5$).
The following line contains $n$ integers $W_i$ ($1 \leq W_i \leq 1000$) separated by a whitespace with the initial values of the vertices.
The following $n-1$ lines contain two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$) separated by a whitespace, indicating that there is an edge between vertices $u$ and $v$.
The next line contains the number of queries $q$ ($1 \leq q \leq 2 \times 10^5$).
The following $q$ lines contain the description of the queries, in the format explained above.
Output
For each query of type $2$, print the value of the vertex $v$ in each case.
Sample test(s)
Input
4
1 2 3 4
1 2
1 3
1 4
5
1 1 3
2 1
2 2
2 3
2 4
Output
1
5
6
7
Input
4
1 2 3 4
1 2
1 3
1 4
6
1 2 3
2 1
2 2
2 3
1 1 4
2 4
Output
4
2
3
8