欢迎来到六轩岛.

黄金的魔女从心底感谢您的到来.

不知准备的红茶和甜点是否符合您口味？

若您感到困倦乏味，妾身准备了一些稍有挑战的谜题，供您消遣时间：

给定一棵以节点 1 为根的有根树.树上有两名选手：Alice 和 Bob. 初始时 Alice 位于节点 A，Bob 位于节点 B（保证 A ≠ B）. 两人轮流行动，Alice 先手.

• 祖先 / 后代 ：均相对根 1 定义.某节点的子树包含其自身及所有后代；某节点的祖先指从该节点沿父指针向上所能到达的所有节点（不含自身），其中与其距离为 1 的祖先称为父节点.
• 标记：Alice 维护自己的标记集合 M_A，Bob 维护自己的标记集合 M_B.两者相互独立.初始两集合为空.一名选手若将某节点加入自己的集合，并不影响对方是否可以在其回合将同一节点加入其集合.
• 代价：当某位选手在其行动中标记了若干节点时，需要支付这些被其标记节点权值之和，记为该选手在本局的总代价. 移动到祖先的操作不需要支付代价.

行动规则:

在自己的回合中，当前选手（位于节点 u）必须选择并执行以下两种操作之一：

1. 向上跳：任选一个祖先 节点 p（可为直接父节点，也可为更高层祖先），将自己的位置从 u 跳至 p. 此操作不产生代价. 若 u 无祖先（即 u = 1），则该操作不可选.
2. 向下标记并跳：任选一个未被该选手标记 的节点 x，要求 x 属于当前节点 u 的子树（包含 u），支付代价 w[x] 将节点 x 加入该选手的标记集合，并将自己的位置从 u 跳至 x.

胜负判定:

• 当执行完某名选手的一次行动后，若两名选手的位置处于同一节点，则执行该次行动的选手立即获胜，对局结束.
• 如果轮到某名选手行动时，他没有任何合法行动（既不能向上跳，也无可标记的子树节点），则其对手立即获胜，对局结束.

可以证明，对局一定在有限步内结束.

在双方都以"使自己获胜"为目标且都采取最优策略的前提下：

1. 判断谁能保证获胜（Alice 或 Bob）.
2. 输出获胜者为确保胜利所需支付的最小总代价,若获胜者在最优策略下无需进行任何标记操作，则代价为 0. 这里只统计最终获胜者在其最优取胜策略下需要支付的总代价；对手的代价不计入.

那么，祝您度过一段愉快的时光.