题面

比赛时一急以为可以加多条边导致没写出来（（

分析

考虑 $f[i][j](1 \le i \le n,j \in {0,1})$ 表示将 $i$ 号点变为先手必败/必胜所需要的最小花费。

初始时先手必胜的点 $f[i][1]=0$，初始时先手必败的点 $f[i][0]=0$。

接下来考虑加边的情况。显然如果一个先手必败点要作为这条加上去的边的起点，那么终点一定是树上所有非祖先先手必败点中 $B \times a_i$ 最小的点。因为一个先手必败点连到另一个先手必败点上后，这个点就会变为先手必胜点。而先手必胜点再往外连边不会使答案更优。如果一个点向自己的一个祖先连边也并不会使答案更优（显然如果你想通过这种方法使自己更优，对手在下一轮也会通过相同的方法使自己更优，造成无限循环）。

这个可以在 DFS 过程中记录。先采用这个方法将所有 $f[i][0]=0$ 的点（先手必败点）的 $f[i][1]$ 赋上值。

接着考虑转移。当一个点的所有孩子节点均为必胜点时这个点为必败点；当一个点存在一个孩子节点为必败点时这个点为必胜点。

如果这个点为必败点，只需要找到一个必败的孩子节点，用它的值来更新自己就可以了。

$$f[i][1]=\min (f[son_i][0])$$

如果这个点要为必胜点，则所有孩子都必须为必败点。如果原来有两个甚至更多的孩子节点是先手必胜的，显然这次就将无法转移（因为我们最多只能让其中的一个孩子节点转变状态）。如果原来没有孩子是先手必胜的，则赋初值时已经考虑该情况。仅当有一个孩子是先手必胜时我们需要在这里进行转移。下面令 $son$ 表示这个儿子。

$$f[i][0]=f[son][1]$$

具体实现见代码。

代码

实现并不是很简单。

可能是因为我的代码实现能力比较弱

/**
 * @author Macesuted
 * @date 2021-03-22
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <bits/stdc++.h>
using namespace std;

using io::getch;
using io::putch;
using io::read;
using io::write;

#define maxn 200005
#define inf 4000000000000000000LL

vector<vector<int> > graph;
int a[maxn];
long long f[maxn][2], minVal[maxn];
int n, t;
long long A, B;

void dfs(int p) {
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) {
        dfs(*i);
        if (f[*i][0] == 0) f[p][1] = 0;
        minVal[p] = min(minVal[p], minVal[*i]);
    }
    if (f[p][1]) f[p][0] = 0, minVal[p] = min(minVal[p], B * a[p]);
    return;
}
void update(int p, long long val) {
    long long best1 = inf, best2 = inf;
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
        if (minVal[*i] < best1)
            best2 = best1, best1 = minVal[*i];
        else if (minVal[*i] < best2)
            best2 = minVal[*i];
    int cnt1 = 0;
    long long cntVal = 0;
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) {
        update(*i, min(val, minVal[*i] == best1 ? best2 : best1));
        f[p][1] = min(f[p][1], f[*i][0]);
        if (!f[*i][0]) {
            cnt1++;
            cntVal = f[*i][1];
        }
    }
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
        val = min(val, minVal[*i]);
    f[p][1] = min(f[p][1], A * a[p] + val);
    if (cnt1 == 1) f[p][0] = min(f[p][0], cntVal);
    return;
}

int main() {
    int T = read<int>();
    while (T--) {
        n = read<int>(), t = read<int>(), A = read<long long>(), B = read<long long>();

        for (register int i = 1; i <= n; i++) f[i][0] = f[i][1] = minVal[i] = inf;

        graph.resize(n + 1);
        for (register int i = 2; i <= n; i++) graph[read<int>()].push_back(i);
        for (register int i = 1; i <= n; i++) a[i] = read<int>();

        dfs(1), update(1, inf);

        write(f[1][!t] == inf ? -1 : f[1][!t]), putch('\n');

        graph.clear();
    }
    return 0;
}