K-黄金魔女的谜题_中国地质大学（武汉）2025年冬新生赛（同步赛）

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

令人怀念，贯穿故乡的鲇川.
欲前往黄金乡的人们，请延此而下，寻找钥匙吧.

顺川而下，终将至『里』.
于其里寻找二人张口之岸.
通往黄金乡之钥匙即沉眠于此.

掌握钥匙之人请遵循以下规则，启程前往黄金乡.

第一晚，将钥匙所选之六人献祭.
第二晚，拆散幸存者中依偎的二人.
第三晚，幸存者们赞颂吾高贵之名.
第四晚，剜头而杀.
第五晚，剜胸而杀.
第六晚，剜腹而杀.
第七晚，剜膝而杀.
第八晚，剜足而杀.
第九晚，魔女复苏，无人生还.
第十晚，旅途结束，将至黄金之乡.

魔女对贤明之人大加赞誉，将赐予以下四样宝物.

其一，黄金乡全部之黄金.
其二，复苏全部亡者之灵魂.
其三，复苏曾经失去之爱.
其四，令魔女回归永远之安眠.

愿汝安详地沉睡……
吾至爱之魔女，贝阿朵莉切.

欢迎来到六轩岛.
黄金的魔女从心底感谢您的到来.
不知准备的红茶和甜点是否符合您口味？

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

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

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

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

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

注：操作 2 中的“未被标记”仅指该名选手自己的标记集合中不包含该节点；对手是否标记过该节点不作限制.

胜负判定:

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

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

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

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

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

输入描述:

第一行包含三个整数 （），表示节点个数、Alice 的初始位置、Bob 的初始位置.

接下来  行，每行两个整数 （），表示无向边 (). 保证这些边构成一棵树.

最后一行包含  个整数 ，其中 () 为标记节点  的代价.

输出描述:

输出两行：

第一行输出字符串或，表示在最优对弈下的必胜方.

第二行输出一个整数，表示该必胜方为保证胜利所需支付的最小总代价.

示例1

输入

复制

输出

复制

Alice
0

说明

样例一中，Alice 直接跳到祖先 1 上与Bob相遇，游戏结束，Alice胜利，总代价为0.

示例2

输入

复制

输出

复制

Bob
2

说明

样例二中，Alice 首先选择操作2，跳到节点 2 并标记，花费代价5；Bob选择操作2，跳到节点 3 并标记，花费代价2；Alice选择操作1，跳到 1；Bob选择操作1，跳到1与Alice相遇，游戏结束，Bob获胜，总代价为2.不存在代价更小的情况.