「EZEC-7」加边

题目背景

> 暴力怎么做?暴力是不是,加边!加边!加边!然后,并查集查询! Alice 不喜欢并查集,但是她喜欢加边。

题目描述

给定一棵 $n$ 个节点的树,节点从 $1$ 开始编号,$1$ 号节点是根节点,每条边的方向是从父亲到儿子。每个点有一个点权 $a_i$。Alice 和 Bob 在玩游戏,他们在根节点上放了一个棋子,Alice 和 Bob 轮流将棋子沿边移动,谁不能移动谁输。 已知 Alice 是先手或是后手。在游戏开始前,Alice 可以在树上添加一条有向边 $u\to v$($1\le u,v\le n$),然后和 Bob 在形成的图上玩这个游戏,她希望自己存在必胜策略。**她也可以选择不加边。如果无法决出胜负则不算胜利。** 给定正整数 $A,B$,Alice 添加边 $u\to v$ 的代价是 $A\times a_u+B\times a_v$。选择不加边的代价为 $0$。 Alice 要最小化她的代价。如果她怎么加边都不满足要求,输出 $-1$。 Alice 会做出 $T$ 次询问,你需要对每个询问输出答案。

输入输出格式

输入格式


**本题有多组数据。** 第一行输入一个正整数 $T$,表示询问次数。 对于每组询问,第一行输入四个正整数 $n,t,A,B$,其中 $n$ 表示树的节点数,$t$ 表示操作顺序,$t=0$ 表示 Alice 先手,$t=1$ 表示 Alice 后手。 接下来一行 $n-1$ 个正整数,第 $i$ 个数表示节点 $i+1$ 的父亲编号 $f_{i+1}$。 接下来一行 $n$ 个正整数,第 $i$ 个表示 $a_i$ 的值。

输出格式


对于每个询问,输出一行一个整数,表示 Alice 的最小代价。如果她怎么加边都不满足要求,输出 $-1$。

输入输出样例

输入样例 #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

-1
0
22
86491

说明

**【样例解释】** 在第 $1$ 组询问中,Alice 是后手,她无论怎么添加边都无法拥有必胜策略,所以输出 $-1$。 在第 $2$ 组询问中,Alice 是后手,她不需要添加边就拥有必胜策略,所以代价为 $0$。 在第 $3$ 组询问中,Alice 是先手,她只能添加一条 $1\to 3$ 的边使自己必胜,此时代价为 $2\times 4+7\times 2=22$。 在第 $4$ 组询问中,Alice 是后手,她可以添加一条 $9\to 5$ 的边使自己必胜,此时代价为 $523\times 109+182\times 162=86491$。她还有其他使自己必胜的方法,但是可以发现 $86491$ 是最小代价。 ------------ **【数据范围】** **本题采用捆绑测试。** - 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):无特殊限制。 对于 $100\%$ 的数据,满足 $1\le T\le 2\times10^3$,$2\le n\le2\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\}$。 ------------ **【提示】** 请使用较快的输入方式。