RT

复杂度 $\mathcal O\left(n \log n\right)$ 自带大常数

链的数据卡点，最后一个 subtask 踩点过

发完贴后我应该去吃饭，违规的话麻烦大家点点举报

#include <bits/stdc++.h>

#define LL __int128

using namespace std;

template <typename Temp> inline void read(Temp & res) {
	Temp fh = 1; res = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
	res = res * fh;
} 

const int Maxn = 2e5 + 5;
const LL INF = 0x7fffffffffffffff / 2;

struct e {
	int to, nxt;
} b[Maxn];
int head[Maxn], ecnt;
void add(int u, int v) {b[++ecnt] = (e) {v, head[u]}; head[u] = ecnt;}

bool g[Maxn], h[Maxn]; LL f[Maxn];

int n, w, x;
LL A, B, a[Maxn];

#define ls t << 1
#define rs t << 1 | 1
LL data[Maxn << 2];
void modify(int pos, LL d, int l, int r, int t) {
	if(l == r) {data[t] = d; return;}
	int mid = (l + r) >> 1;
	if(pos <= mid) modify(pos, d, l, mid, ls);
	else modify(pos, d, mid + 1, r, rs);
	data[t] = min(data[ls], data[rs]);
}
#undef ls
#undef rs

void dfs1(int t) {
	int cnt = 0;
	for(int i = head[t]; i; i = b[i].nxt) {
		dfs1(b[i].to);
		if(!g[b[i].to]) cnt++;
	}
	if(cnt == 0) g[t] = 0, h[t] = 0;
	else g[t] = 1, h[t] = (cnt == 1);
	return;
}

void dfs2(int t) {
	if(g[t] == 0) modify(t, INF, 1, n, 1);
	for(int i = head[t]; i; i = b[i].nxt) {
        dfs2(b[i].to);
        if(!g[t]) f[t] = min(f[t], f[b[i].to]);
        else if(h[t]) {
            if(!g[b[i].to]) f[t] = f[b[i].to];
        }
    }
    if(!g[t]) f[t] = min(f[t], A * a[t] + B * data[1]);
	if(g[t] == 0) modify(t, a[t], 1, n, 1);
}

void Main() {
	read(n); read(w); read(A); read(B); ecnt = 0;
	for(int i = 1; i <= n; ++i) head[i] = 0, f[i] = INF;
    for(int i = 1; i <= (n << 2); ++i) data[i] = INF;
	for(int i = 2; i <= n; ++i) read(x), add(x, i);
	for(int i = 1; i <= n; ++i) read(a[i]);
	dfs1(1);
    if((w == 0 && g[1]) || (w == 1 && (!g[1]))) {printf("0\n"); return;}
	for(int i = 1; i <= n; ++i) if(!g[i]) modify(i, a[i], 1, n, 1);
	dfs2(1);
	printf("%lld\n", (f[1] != INF ? f[1] : -1));
	return;
}

int main() {
	int T; read(T);
	while(T--) Main();
	return 0;
}