P7443 「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$ 次询问，你需要对每个询问输出答案。

无

无

**【样例解释】** 在第 $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