P11855 [CSP-J 2022 Shandong] Deployment

Due to the impact of the pandemic, Shandong Province canceled the CSP-J 2022 certification event, and re-created the problems in March of the following year to hold a make-up contest within the province.

“Letters from afar never cease; beacon fires pass through five passes even in daylight.” In ancient times, without modern information-based warfare technology, people could only rely on beacon fires to transmit messages and on generals to plan and deploy troops to gain an advantage in war. To minimize consumption, Country A has now built roads and marching deployment routes among $n$ cities, such that all $n$ cities are mutually reachable and there are no cycles (i.e., they form a tree structure rooted at City $1$). Each city has a certain number of troops stationed. To describe the problem clearly, we number these $n$ cities from $1$ to $n$, and City $1$ is the root of the tree (the testdata guarantees that they form a tree rooted at City $1$). Initially, City $i$ has an initial troop count of $a_{i}$. Now, to test the speed of war deployment, the general performs $m$ tests. Each test is one of the following two commands: `1 x y` (the three numbers are separated by exactly 1 space): add $y$ troops to City $x$ **and** to all cities in the subtree rooted at it. `2 x y` (the three numbers are separated by exactly 1 space): add $y$ troops to City $x$ **and** to all cities directly connected to it (including its parent node and child nodes). After issuing the $m$ commands, the general calls in an adviser and makes $q$ queries. Each query asks for the final troop count of City $x$. That adviser is Xiao Xiamai, and he asks you for help again. Please help him solve the problem (the results of the $q$ queries).

The first line contains a positive integer $n$, indicating the number of cities. The second line contains $n$ positive integers $a_{1},a_{2},\dots a_{n}$, indicating the initial troop count in each city. The next $n-1$ lines each contain two integers $x,y$, indicating that there is a road directly connecting cities $x$ and $y$. The next line contains a positive integer $m$, indicating the number of commands. The next $m$ lines each contain three positive integers $p,x,y$, representing one of the two command types. When $p=1$, it means the first command; when $p=2$, it means the second command. The next line contains a positive integer $q$, indicating the number of queries. The next $q$ lines each contain a positive integer $x$, indicating a query for the final troop count of the city numbered $x$.

Output $q$ lines. Each line contains a positive integer, corresponding to the answer for each query.

### Constraints For $30\%$ of the testdata, $1\le n\le1000,1\le m\le1000$. For $60\%$ of the testdata, $1\le n\le10^{5},1\le m\le10^{5},1\le q\le10^{5}$. Among them, for $10\%$ of the testdata the tree is a chain; for another $10\%$ the testdata contains only operation $1$; for another $10\%$ the testdata contains only operation $2$. For $100\%$ of the testdata, it is guaranteed that the given cities and roads form a tree, and City $1$ is the root node. $1\le n\le10^{6},1\le m\le10^{6},1\le q\le10^{6},1\le a_{i}\le10^{9},1\le x\le n,1\le y\le10$. Hack testdata set added on 2025-06-26. Translated by ChatGPT 5