P3727 Manhattan Project E

In June 1942, the United States began the plan to develop an atomic bomb using nuclear fission reactions, also known as the Manhattan Project. Later, two atomic bombs exploded in Hiroshima and Nagasaki. The world witnessed the power of nuclear weapons and trembled under their threat. In the year 2200, the dedsec organization infiltrated the U.S. nuclear weapon system by exploiting cybersecurity vulnerabilities, plotting to use the nuclear stockpile hidden in Manhattan to destroy the world. However, a dedsec member, Badboy17, opposed the plan and informed Aiden. To save his family and prevent Earth from becoming a wasteland, Aiden had to once again use his hacking skills to save the world. 

Aiden tries to hack into dedsec’s system and seize control, but dedsec responds and fights back. The dedsec network can be regarded as a connected graph with $n$ nodes and $n-1$ edges (a tree). Each node has a stability value. Aiden may choose a chain (a simple path) in the network and hack all nodes on that chain (i.e., detach that chain from the tree). Suppose the chain has length $m$ (i.e., it contains $m$ nodes). You will then obtain $m$ nodes, and the game is played only on these $m$ nodes. Aiden and dedsec then start a battle of moves. They take turns. Each move, a player may choose any node with a stability value greater than $0$ and perform an operation according to the rules below. After the operation, the stability value of that node must not become less than $0$, otherwise the computer will explode. The player who cannot make a move loses. Because dedsec has the advantage of defense, dedsec moves first. Although Aiden is skilled at hacking, his phone ran out of battery. He has sent this information to you, hoping you can help save the world. You need to write a program to determine whether there exists a way for Aiden to win. Of course, dedsec’s defense might be flawless, and Aiden may not be able to win at all—in that case, you’ll have to run to the shelter and become a test subject.

The input contains multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case: - The first line contains an integer $n$, the number of nodes. - The next $n-1$ lines each contain two integers $u, v$, indicating an edge between $u$ and $v$ in the network. - The next line contains $n$ integers $w_1, w_2, \dots, w_n$, where $w_i$ denotes the stability value of node $i$. - The next line contains an integer $k$, describing the move rules: - If $k=1$, you may decrease the stability by any positive integer. - If $k=2$, the next line contains a positive integer $s$, and each move may decrease the stability by a non-negative integer power of $s$. - If $k=3$, the next line contains a positive integer $s$, and each move may decrease the stability by any integer greater than or equal to $s$. - If $k=4$, each move you may either decrease the stability by any positive integer, or split a node with stability at least $2$ into two nodes whose stability values sum to the original (for example, split $7$ into $3+4$). - If $k=5$, neither player can make any move.

For each test case, output one line: If there exists a way for you to win, output `Mutalisk ride face how to lose?`. If there is no way to win, output `The commentary cannot go on!`.

| Test point | $n \le$ | $k$ | $w_i \le$ | |:-:|:-:|:-:|:-:| | $1$ | $50$ | $1$ | $10^3$ | | $2$ | $3 \times 10^4$ | $1$ | $10^3$ | | $3$ | $300$ | $3$ | $10^6$ | | $4$ | $10^3$ | $4$ | $10^6$ | | $5$ | $3 \times 10^4$ | $1$ | $10^9$ | | $6$ | $3 \times 10^4$ | $2$ | $10^9$ | | $7$ | $3 \times 10^4$ | $3$ | $10^9$ | | $8$ | $3 \times 10^4$ | $3$ | $10^9$ | | $9$ | $3 \times 10^4$ | $4$ | $10^9$ | | $10$ | $3 \times 10^4$ | $4$ | $10^9$ | For $100\%$ of the testdata, $T \le 5$. All inputs are positive integers. Translated by ChatGPT 5