「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\}$。
------------
**【提示】**
请使用较快的输入方式。