#P3727. 曼哈顿计划E

    ID: 2694 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>点分治洛谷原创枚举分治深度优先搜索,DFS

曼哈顿计划E

题目背景

1942 年 6 月,美国开始实施利用核裂变反应来研制原子弹的计划,亦称曼哈顿计划。后来两颗原子弹在广岛和长崎爆炸,世界见证了核武器的威力,并在它的威胁下颤抖不已。2200 年,dedsec 组织利用美国军方的网络安全漏洞渗入了美国的和武器系统,并密谋使用隐藏在曼哈顿的核武器储备毁灭世界。然而 dedsec 的一名成员 Badboy17 反对这一计划,她把这一计划告知了艾登。为了拯救他的家人,避免地球变为废土,艾登不得不再次发挥他的黑客能力拯救世界。

题目描述

艾登尝试黑入 dedsec 的系统并取得控制权,然而 dedsec 有所反应并予以反击。

dedsec 的网络可以看做是一个 nn 个点 n1n-1 条边的连通图(一棵树),每个节点有一个稳定值。

艾登可以选择网络中上的一条链,并对那一条链上的节点进行破解(把这一条链从树上拆下来)。

假设这一条链长度为 mm,现在你会得到 mm 个节点。

然后艾登要和 dedsec 开始攻防战,双方轮流行动,每次可以从任意一个稳定值大于 00 的节点里依照计算规则进行一些操作,操作后,稳定值不能小于 00,否则计算机会爆炸,最后不能进行操作的一方算作失败

由于 dedsec 占据了防守的地理优势,dedsec 先进行操作

艾登虽然精于黑客技术,但他的手机没电了。现在他把这个消息告诉了你,希望你帮他拯救世界,所以你需要写一个程序,来帮你判断是否存在一种方式,艾登可以取胜。当然,dedsec 的防守可能完美无缺,艾登根本无法取胜,你只好跑到 shelter 里去当试验品。

输入格式

输入包含多组测试数据,输入第一行包含一个整数 TT,表示数据组数。

对于每组测试数据,第一行一个整数 nn,表示有 nn 个点。

第二行至第 nn 行,每行两个整数 u,vu,v,表示网络中有一条边连接 u,vu,v

n+1n+1nn 个整数 ww,第 wiw_i 表示 ii 号节点的稳定值。

n+2n+2 行一个整数 kk,描述操作的规则:

  • 如果 k=1k=1,你可以减少任意正整数的稳定值。
  • 如果 k=2k=2,接下来一行一个正整数 ss,表示双方每次可以减少 ss 的非负整数幂的稳定值。
  • 如果 k=3k=3,接下来一行一个正整数 ss,表示双方每次可以减少大于等于 ss 的稳定值。
  • 如果 k=4k=4,表示双方每次可以减少任意正整数的稳定值,或者把一个稳定值数量大于等于 22 的节点分裂成两个,分开后的两个节点的稳定值之和等于原来的节点(比如 77 分成 3+43+4)。
  • 如果 k=5k=5,双方都不能进行操作。

输出格式

对于每一组测试数据,输出一行:

如果存在一种方式,你可以获胜,输出 Mutalisk ride face how to lose?

如果不存在一种方式可以取胜,输出 The commentary cannot go on!

1
3
1 2
2 3
1 2 3
1
Mutalisk ride face how to lose?
1
3
1 2
2 3
1 2 4
1
The commentary cannot go on!

提示

测试点 nn\le kk wiw_i\le
11 5050 11 10310^3
22 3×1043\times 10^4
33 300300 33 10610^6
44 10310^3 44
55 3×1043\times 10^4 11 10910^9
66 22
77 33
88
99 44
1010

对于 100%100\% 的数据,T5T\le 5

保证输入均为正整数