P9133 [THUPC 2023 初赛] 大富翁

有一天，小 W 和小 H 在玩大富翁。

这版大富翁的游戏规则比较独特。它的地图是一棵 $n$ 个节点的有根树，其中 $1$ 号节点为根。树上每个节点都有一个价格，第 $x$ 号节点的价格记为 $w_x$。 对于树上两个不同的节点 $x,y$，若 $x$ 是 $y$ 的祖先节点（即，$x$ 在 $1$ 号点到 $y$ 号点的简单路径上），则称 $x$ **支配** $y$。 游戏过程中，小 W 和小 H 轮流**购买**树上的一个未被人购买过的节点，直到树上的 $n$ 个节点都被小 W 或小 H 购买。（游戏开始前，树上的所有节点都没有被购买。） 对于一次购买，假设买方购买了 $x$ 号节点，那么他首先要向系统支付 $w_x$ 个游戏币。假设此时 $x$ 支配着 $n_1$ 个已被买方的对手购买了的节点，同时又被 $n_2$ 个已被对手购买了的节点支配。若 $n_1>n_2$，那么对手要向买方支付 $n_1-n_2$ 个游戏币，若 $n_1

无

无

#### 样例解释 1 一个可能的游戏过程是： - 第一次购买：小 W 购买 $1$ 号节点，向系统支付 $0$ 个游戏币。 - 第二次购买：小 H 购买 $2$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。 - 第三次购买：小 W 购买 $3$ 号节点，向系统支付 $1$ 个游戏币。 - 第四次购买：小 H 购买 $4$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。 - 第五次购买：小 W 购买 $6$ 号节点，向系统支付 $0$ 个游戏币。 - 第六次购买：小 H 购买 $5$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。 - 第七次购买：小 W 购买 $7$ 号节点，向系统支付 $0$ 个游戏币。 #### 子任务 对于所有测试数据，$1\leq n\leq 2\times 10^5$，$0\leq w_x\leq 2\times 10^5$。保证输入的图为一棵以 $1$ 号节点为根的有根树。 #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。 题解等资源可在 查看。