題目 ?：Gameia：鏈接

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 160????Accepted Submission(s): 53

Problem Description Alice and Bob are playing a game called 'Gameia ? Gameia !'. The game goes like this :
0. There is a tree with all node unpainted initial.
1. Because Bob is the VIP player, so Bob has K chances to make a small change on the tree any time during the game if he wants, whether before or after Alice's action. These chances can be used together or separate, changes will happen in a flash. each change is defined as cut an edge on the tree.
2. Then the game starts, Alice and Bob take turns to paint an unpainted node, Alice go first, and then Bob.
3. In Alice's move, she can paint an unpainted node into white color.
4. In Bob's move, he can paint an unpainted node into black color, and what's more, all the other nodes which connects with the node directly will be painted or repainted into black color too, even if they are white color before.
5. When anybody can't make a move, the game stop, with all nodes painted of course. If they can find a node with white color, Alice win the game, otherwise Bob.
Given the tree initial, who will win the game if both players play optimally?
Input The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with two integers N and K : the size of the tree and the max small changes that Bob can make.
The next line gives the information of the tree, nodes are marked from 1 to N, node 1 is the root, so the line contains N-1 numbers, the i-th of them give the farther node of the node i+1.

Limits
T≤100
1≤N≤500
0≤K≤500
1≤Pi≤i
Output For each test case output one line denotes the answer.
If Alice can win, output "Alice" , otherwise "Bob".
Sample Input 2 2 1 1 3 1 1 2
Sample Output Bob Alice 題解：- 如果Bob能把這棵樹分成若干兩個一組的點對，那么Bob取得勝利，否則Alice獲勝。

?- 如果原樹不存在兩兩匹配的方案，Alice從樹葉開始，每次都染樹葉父節點，Bob被迫只能不斷的染葉子，Bob退化成一般玩家，因為Bob做不做小動作都不會逆轉局勢，總會出現一個時間點Bob沒辦法跟上Alice的節奏而讓Alice染到一個周圍都已被染色的孤立點（因為原樹不存在兩兩匹配的方案）?

- 如果原樹存在兩兩匹配的方案，而且Bob的小動作次數也足以把原樹分成兩兩的點對，那么Bob顯然獲勝。 - 如果原樹存在兩兩匹配的方案，而Bob的小動作不足以把樹分成兩兩的點對，Alice一定獲勝，因為每次染某個葉子節點（該節點為其父節點的唯一子節點），Alice總能迫使Bob不斷的做小動作以保證剩下的樹不會出現奇數節點的樹，且每次小動作割出一個點對（包含Alice剛染的點），最后有兩種情況。

?- 出現某個結點有>=2個子節點為葉子節點。Alice染這個點，Bob跟不上Alice的節奏，出現孤點，Ailice取勝

?- 否則整個過程一定會持續到樹被染光或者Bob被Alice掏空導致做不了小動作進而被迫割出一塊size為奇數的子樹（這棵樹顯然沒辦法兩兩匹配）而敗北。

?- Bob被允許“任意時刻”做小動作看似很厲害其實很雞肋，把問題改成“Bob只能在游戲開始之前做小動作”會得到同樣的結論。 - “氪不改命，玄不救非” 時間復雜度 $O(n)$

我的理解：經過長時間的思考確實，Bob的k次斷線必須維持所剩節點為偶，若為偶，那么白棋下在葉節點，使得再下的黑棋多染一個節點，使所剩棋子為奇數，為了不多染一個棋子，那么Bob要斷線避免所剩棋子數為奇數個。

Bob贏得方法只有一個，在開始之前先用他的k次斷線，將樹分成兩兩匹配，才能贏，否則Bob輸。

兩兩匹配方法，應該是從葉節點上往上匹配，所以父節點必須在孩子節點匹配以后再匹配（拓撲排序），沒有匹配的節點都應該和他的父親匹配，那么只需要判斷他（他自己沒有染色，并且他的兒子都已經匹配過）的父親是否被染色了即可，若未染色，則將他和他的父親都染上色，否則他沒法完成配對，則一定是白棋贏。

若兩兩可以匹配則判斷k次斷線是否夠，不夠則白贏；

我的AC代碼：

#include<stdio.h> #include <iostream> #include<string.h> #include<algorithm> #include<cmath> #include<map> #define LL long long using namespace std; int a[600];//a[i]=x表示節點i的父節點是x int b[600];//染色標記 int topo[600];//排序后的節點順序 int c[600][600];//c[i][j]=x代表節點i的第j個兒子是節點x; int s[600];//s[i]=x代表節點i有x個兒子 int cnt; void toposort(int d) {for(int i=0;i<s[d];i++) toposort(c[d][i]);//先將d節點的兒子排序topo[cnt++]=d;//然后再放節點dreturn ; } int main() {int t;scanf("%d",&t);while(t--){memset(b,0,sizeof(b));memset(s,0,sizeof(s));cnt=0;b[0]=1;a[1]=0;//因為1節點沒有父節點，為了避免特判，所以給1添個已經染色的父節點0；不影響結果。int n,k;scanf("%d%d",&n,&k);for(int i=2; i<=n; i++){scanf("%d",&a[i]);c[a[i]][s[a[i]]++]=i;}int flag=0;if(n%2) flag=1;//節點數為奇數一定是白贏if(!flag) toposort(1);if(!flag)for(int i=0; i<n; i++)if(!b[topo[i]]){if(b[a[topo[i]]]){flag=1;break;}else{b[a[topo[i]]]=1;b[topo[i]]=1;}}if(!flag) if(n/2-1>k) flag=1;//判斷k次夠不夠if(flag) printf("Alice\n");else printf("Bob\n");} }

總結

以上是生活随笔為你收集整理的HDU 6105 Gameia 树上博弈（思路题）（内附官方题解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。