24661번 - Items and Heroes 다국어

There is a rooted tree of $N$ vertices. The vertices are numbered by integers from $1$ to $N$, with vertex $1$ as the root. The parent of vertex $i$ ($2 \le i \le N$) is denoted as $P_i$.

Each vertex has a box with items. Also, there is a hero in each vertex.

In the beginning, the box in vertex $i$ contains $A_i$ items.

In each vertex $i$, the hero from that vertex has the quest to collect $C_i$ items. The hero in vertex $i$ can choose some vertices from the subtree rooted at vertex $i$ and take as many items as she wants from each of the selected vertices. One item cannot be taken by more than one hero.

Determine if it is possible for the heroes to act in such a way that all $N$ quests will be completed.

Additionally, $Q$ queries are given. In the $j$-th query, the integers $t_j$, $v_j$, $x_j$ are given, and the values are changed as follows:

• If $t_j=1$, change the value of $A_{v_j}$ to $x_j$.
• If $t_j=2$, change the value of $C_{v_j}$ to $x_j$.

The queries are applied sequentially. The changes made in each query remain for all the subsequent queries as well. After each query, determine if it is possible to complete all $N$ quests.

The first line of input contains one integer $N$ ($1 \le N \le 10^5$).

The second line contains $N-1$ integers $P_2, P_3, \ldots, P_N$: the parents of vertices $2, 3, \ldots, N$ ($1 \le P_i < i$).

The third line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^9$).

The fourth line contains $N$ integers $C_1, C_2, \ldots, C_N$ ($1 \le C_i \le 10^9$).

The fifth line contains one integer $Q$ ($1 \le Q \le 10^5$).

Each of the following $Q$ lines contains one query described by three integers $t_j$, $v_j$ and $x_j$ ($1 \le t_i \le 2$, $1 \le v_i \le N$, $1 \le x_i \le 10^9$): the type of the query, the number of vertex and the new value for $A_{v_i}$ (for the query of the first type) or $C_{v_i}$ (for the query of the second type), respectively.

On the first line, print "Yes" if it is possible to complete all $N$ quests at once, or "No" otherwise.

On the following $Q$ lines, print the answers for the queries in the same format, one per line.

In Example 1, the hero from vertex 1 takes two items from the box at vertex 1 and one item from the box at vertex 3, the hero from vertex 2 takes an item from the box at vertex 2, and the hero from vertex 3 takes two items from the box at vertex 3. So, all three quests are completed.

The first query changes the number of items in the box at vertex 1 from two to one. In this case, there are not enough items to complete all three quests.

The second query changes the number of items to complete the quest for the hero at vertex 3 from two to one. In this case, the hero at vertex 1 takes one item from the box at vertex 1 and two items from the box at vertex 3, the hero at vertex 2 take one item from the box at vertex 2, the hero at vertex 3 takes one item from the box at vertex 3, and all three quests are again completed.