Background

How do you do brute force? Brute force is, add edges! Add edges! Add edges! Then query with DSU!

Alice does not like DSU (Disjoint Set Union), but she likes adding edges.

Problem Description

Given a tree with $n$ nodes, the nodes are numbered starting from $1$. Node $1$ is the root. Each edge is directed from the parent to the child. Each node has a weight $a_i$. Alice and Bob are playing a game: they place a token on the root node. Alice and Bob take turns moving the token along directed edges. Whoever cannot move loses.

It is known whether Alice moves first or second. Before the game starts, Alice may add one directed edge $u\to v$ ($1\le u,v\le n$), and then they play the game on the resulting graph. She wants to have a winning strategy. She may also choose not to add an edge. If the winner cannot be determined, it does not count as a win.

Given positive integers $A,B$, the cost for Alice to add an edge $u\to v$ is $A\times a_u+B\times a_v$. The cost of choosing not to add an edge is $0$.

Alice wants to minimize her cost. If no matter how she adds an edge she cannot meet the requirement, output $-1$.

Alice will make $T$ queries. You need to output the answer for each query.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of queries.

For each query, the first line contains four positive integers $n,t,A,B$, where $n$ is the number of nodes in the tree, and $t$ indicates the move order: $t=0$ means Alice moves first, and $t=1$ means Alice moves second.

The next line contains $n-1$ positive integers. The $i$-th number is the parent index $f_{i+1}$ of node $i+1$.

The next line contains $n$ positive integers. The $i$-th number is the value of $a_i$.

Output Format

For each query, output one integer per line, the minimum cost for Alice. If no matter how she adds an edge she cannot meet the requirement, output $-1$.

4
3 1 2 7
1 1
4 3 2
3 1 2 7
1 2
4 3 2
3 0 2 7
1 2
4 3 2
9 1 523 182
1 1 2 2 2 3 3 1
3 23 18 293 162 483 574 384 109

-1
0
22
86491

Hint

[Sample Explanation]

In the $1$-st query, Alice moves second. No matter how she adds an edge, she cannot have a winning strategy, so output $-1$.
In the $2$-nd query, Alice moves second. She already has a winning strategy without adding an edge, so the cost is $0$.
In the $3$-rd query, Alice moves first. She can only add an edge $1\to 3$ to guarantee a win. The cost is $2\times 4+7\times 2=22$.
In the $4$-th query, Alice moves second. She can add an edge $9\to 5$ to guarantee a win. The cost is $523\times 109+182\times 162=86491$. She has other ways to guarantee a win, but $86491$ is the minimum cost.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 points): $n\le 10$, $T=1$.
• Subtask 2 (15 points): $\sum n\le 200$.
• Subtask 3 (15 points): $\sum n\le 2000$.
• Subtask 4 (10 points): $f_i=i-1$.
• Subtask 5 (10 points): $f_i=1$.
• Subtask 6 (20 points): $\sum n\le 5\times 10^5$.
• Subtask 7 (20 points): no special restrictions.

For $100\%$ of the data, $1\le T\le 2\times10^3$, $2\le n\le 2\times 10^5$, $\sum n\le 5\times 10^6$, $1\le a_i,A,B\le 10^9$, $f_i<i$, $t\in\{0,1\}$.

[Hint]

Please use a fast input method.

Translated by ChatGPT 5