求调
查看原帖
求调
555381
zlttcl楼主2024/3/3 17:07
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, t, U, V, w[N], minu[N], minv[N], ls[N], rb[N], fa[N], siz[N], ans;
bool vis[N];
ll win[N];
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
inline void dfs(int u, bool op){
	vis[u] = op;
	if(!siz[u]) return;
	if(!op && win[u] != 1) return;
	for(int i = ls[u]; i; i = rb[i]) if(op || !win[i]) dfs(i, !op);
}
inline void solve(){
	n = read(), t = read(), U = read(), V = read();
	for(int i = 1; i <= n; ++ i) vis[i] = win[i] = ls[i] = rb[i] = 0, minu[i] = minv[i] = 0x3F3F3F3F;
	for(int i = 2; i <= n; ++ i){
		fa[i] = read();
		rb[i] = ls[fa[i]];
		ls[fa[i]] = i;
		++ siz[fa[i]];
	}
	for(int i = 1; i <= n; ++ i) w[i] = read();
	for(int i = n; i >= 1; -- i) if(!win[i]) ++ win[fa[i]];
	if((win[1] != 0) ^ t){
		write(0), putchar('\n');
		return;
	}
	dfs(1, !t);
	ans = 0x3F3F3F3F3F3F3F3Fll;
	for(int i = n; i >= 1; -- i){
		if(vis[i]) minu[i] = min(minu[i], w[i]);
		if(!win[i]) minv[i] = min(minv[i], w[i]);
		if(!siz[i]) continue;
		ll u = minu[ls[i]], v = minv[ls[i]];
		for(int j = rb[ls[i]]; j; j = rb[j]){
			if(u != 0x3F3F3F3F && minv[j] != 0x3F3F3F3F) ans = min(ans, U * u + V * minv[j]);
			if(v != 0x3F3F3F3F && minu[j] != 0x3F3F3F3F) ans = min(ans, V * v + U * minu[j]);
			u = min(u, minu[j]), v = min(v, minv[j]);
		}
		minu[i] = min(minu[i], u), minv[i] = min(minv[i], v);
		if(vis[i] && v != 0x3F3F3F3F) ans = min(ans, U * w[i] + V * v);
	}
	write(ans == 0x3F3F3F3F3F3F3F3Fll ? -1 : ans), putchar('\n');
}
signed main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
    int T = read();
    while(T --) solve();
	return 0;
}

2024/3/3 17:07
加载中...