Winning Move in the Tree Game

Alice and Bob play a token‐moving game on a rooted tree. The tree has n nodes numbered from 1 to n with node 1 as the root. Each directed edge goes from a parent to a child. Every node i has an associated weight a_i. A token is placed at the root. In each turn the player whose turn it is must move the token along one of the outgoing edges. The first player who is unable to move loses. (Note that if the game does not terminate – i.e. if it leads to a cycle – then it is not considered a win.)

Before the game starts, Alice can add at most one extra directed edge in the tree, from some node u to some node v (1 ≤ u, v ≤ n), at a cost of A × a_u + B × a_v. Alice is also allowed to choose not to add any edge (this costs 0). It is known whether Alice is the first or the second to move. Alice wishes to secure a forced win under perfect play with a game that eventually terminates, and she wants to minimize her cost. If no edge addition (or no addition at all) can guarantee her victory, output -1.

You are given T queries. In each query the turn order for the game is specified. For each query, determine the minimum cost for Alice to guarantee a win.

Note on game outcome: The game is played on the directed graph (the original tree plus the optional extra edge). A position is a pair (node, turn) where turn = 0 or 1 indicates the player whose turn it is. A position is winning if the player to move can force a win (that is, force the play to eventually end with the opponent unable to move) regardless of the opponent’s responses. If the game may continue forever (i.e. end in a draw), that configuration is not considered a win.

Determining outcomes in a directed graph: For each state (v, turn), moves go from (v, turn) to (w, 1-turn) for every edge v → w. Terminal states (with no moves) are losing for the player whose turn it is. Using retrograde analysis (taking draws into account), one can determine if a state is winning or losing. In this problem, only positions that are forced wins (and terminate) are considered winning.

inputFormat

The first line contains four integers n, T, A, B where n is the number of nodes in the tree, T is the number of queries, and A and B are positive cost factors.

The second line contains n integers a₁, a₂, …, a_n representing the weight of each node.

Each of the next n − 1 lines contains one integer. For i = 2, 3, …, n, the i-th of these lines contains an integer p (1 ≤ p ≤ n) indicating that there is an edge from node p to node i in the tree.

Each of the next T lines contains one integer f (either 0 or 1). If f = 1, it means Alice is the first to move; if f = 0, then Bob moves first.

outputFormat

Output T lines. For each query, print the minimum cost for Alice to guarantee a win. If no edge addition (or no addition at all) can secure a win, print -1.

sample

3 2 1 1
1 2 3
1
1
1
0

0
0