UVa 12033 Game of CS

题目描述Jolly\texttt{Jolly}Jolly和Emily\texttt{Emily}Emily在纸上画了一棵有根树结点编号为000到n−1n - 1n−1000为根。每条边带有权值www表示该边有www个相同的单位。初始时所有边均未涂色。游戏规则如下Emily\texttt{Emily}Emily先手双方轮流操作。每轮玩家可以选择一条边该边至少有一个单位尚未涂色并且从根结点出发仅通过空闲边即尚未被完全涂色的边可以到达该边。Emily\texttt{Emily}Emily用红色涂一个单位Jolly\texttt{Jolly}Jolly用绿色涂一个单位。无法找到可涂边的玩家输掉游戏。给定树的结构和边权双方均采取最优策略求获胜者。输入格式第一行一个整数TTTT≤500T \le 500T≤500表示测试用例数。每个测试用例第一行一个整数nnn2≤n≤10002 \le n \le 10002≤n≤1000。接下来n−1n - 1n−1行每行三个整数uuu、vvv、www0≤u,vn0 \le u, v n0≤u,vnu≠vu \ne vuv1≤w≤1091 \le w \le 10^91≤w≤109表示一条无向边及其权值。输入保证构成一棵有效的树。数据量较大建议使用快速I/O\texttt{I/O}I/O。输出格式对于每个测试用例输出Case x: Emily或Case x: Jolly其中xxx为从111开始的测试用例编号。样例输入4 4 0 1 1 1 2 1 0 3 2 5 0 1 1 1 2 2 0 3 3 0 4 7 3 0 1 1 0 2 1 4 0 1 1 1 2 1 1 3 1输出Case 1: Emily Case 2: Emily Case 3: Jolly Case 4: Emily题目分析本题是一个双人完全信息博弈且游戏状态可以用树的结构和每条边的剩余涂色单位数描述。直接模拟状态空间不可行边权可达10910^9109。需要利用博弈论中的Sprague-Grundy\texttt{Sprague-Grundy}Sprague-GrundySG\texttt{SG}SG定理来化简。观察游戏规则玩家只能涂那些从根出发、路径上的边都未被完全涂满的边。这等价于若某条边被完全涂满则其子树中的边位于该边下方的边将永远无法再被涂色因为从根到它们必须经过这条已被封闭的边。因此游戏过程可以看作是在树上从根向下逐步“封锁”边的过程。每条边一旦被完全涂满就切断其下方所有边与根的联系。这种结构非常适合用递归的SG\texttt{SG}SG值来描述。对于一棵子树其博弈状态仅取决于该子树根结点与其父结点之间的那条边即“入口边”的剩余单位数以及该子树内所有子结点的SG\texttt{SG}SG值。由于每条边的权值可能很大但SG\texttt{SG}SG值的计算只涉及奇偶性和111的特殊情况因此可以高效求解。解题思路我们定义g(u)g(u)g(u)为以结点uuu为根的子树包含从uuu到其子结点的所有边的SG\texttt{SG}SG值。考虑结点uuu与其父结点ppp之间的边eee其权值为www。我们关心的游戏是从根000出发只有经过eee才能进入uuu的子树。在eee被完全涂满之前玩家可以选择在eee上涂色也可以选择进入uuu的子结点对应的边进行涂色。一旦eee被涂满uuu子树的所有边都被隔绝游戏结束。设CCC为uuu的所有子结点vvv的SG\texttt{SG}SG值g(v)g(v)g(v)的异或和即C⨁v∈children(u)g(v)C \bigoplus_{v \in \textit{children}(u)} g(v)C⨁v∈children(u)​g(v)。那么整个以uuu为根、入口边权为www的子博弈可以看作一个组合游戏其SG\texttt{SG}SG值g(u)g(u)g(u)由www和CCC共同决定。通过归纳分析可得如下结论若w1w 1w1则该边只有一个单位必须等所有子博弈结束后才能涂这最后一个单位相当于在子博弈的SG\text{SG}SG值CCC基础上再增加一步因此g(u)C1g(u) C 1g(u)C1。若www为偶数则该边的涂色操作不会改变子博弈的奇偶性整体SG\texttt{SG}SG值不变即g(u)Cg(u) Cg(u)C。若www为奇数且w1w 1w1则每次在该边上涂色都会翻转子博弈SG\texttt{SG}SG值的最低位最终效果等价于将CCC异或上111即g(u)C⊕1g(u) C \oplus 1g(u)C⊕1。这一定理的严格证明可以通过对www的归纳和SG\texttt{SG}SG函数的定义完成此处不再赘述。因此我们只需从叶子结点向上递归计算每个结点的ggg值。对于根结点000它没有父边整个游戏的SG\texttt{SG}SG值即为所有子结点g(v)g(v)g(v)的异或和即CCC的值。若该异或和非零则先手Emily\texttt{Emily}Emily必胜否则Jolly\texttt{Jolly}Jolly必胜。算法步骤以000为根通过DFS\texttt{DFS}DFS遍历树建立父子关系。对于每个结点uuu递归计算其所有子结点vvv的g(v)g(v)g(v)并求异或和CCC。若uuu不是根则根据父边权值www计算g(u)g(u)g(u)若uuu是根则直接将CCC作为整棵树的SG\texttt{SG}SG值。若整棵树的SG\texttt{SG}SG值为000则后手Jolly\texttt{Jolly}Jolly获胜否则先手Emily\texttt{Emily}Emily获胜。时间复杂度每个结点访问一次DFS\texttt{DFS}DFS复杂度O(n)O(n)O(n)满足n≤1000n \le 1000n≤1000的要求。空间复杂度O(n)O(n)O(n)。代码实现// Game of CS// UVa ID: 12033// Verdict: Accepted// Submission Date: 2026-07-13// UVa Run Time: 0.080s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;llsgFunc(ll w,ll c){if(w1)returnc1;if(w%20)returnc;returnc^1;}voiddfs(intu,intparent,ll parentWeight,vectorvectorpairint,lladj,vectorllsg,lltotalXor){ll childXor0;for(autoe:adj[u]){intve.first;ll we.second;if(vparent)continue;dfs(v,u,w,adj,sg,totalXor);childXor^sg[v];}if(u0){totalXorchildXor;sg[0]childXor;}else{sg[u]sgFunc(parentWeight,childXor);}}intmain(){intT;scanf(%d,T);for(intcaseNo1;caseNoT;caseNo){intn;scanf(%d,n);vectorvectorpairint,lladj(n);for(inti0;in-1;i){intu,v;ll w;scanf(%d %d %lld,u,v,w);adj[u].push_back({v,w});adj[v].push_back({u,w});}vectorllsg(n,0);ll totalXor0;dfs(0,-1,0,adj,sg,totalXor);printf(Case %d: %s\n,caseNo,totalXor?Emily:Jolly);}return0;}总结本题的关键在于将复杂的博弈过程转化为可递归计算的SG\texttt{SG}SG值并利用奇偶性简化边权的影响。主要技巧识别游戏的有向树结构利用SG\texttt{SG}SG定理分解子游戏。对边权进行分类111、偶数、奇数111并推导出对应的SG\texttt{SG}SG值公式。使用深度优先遍历自底向上计算避免指数级状态。该解法简洁高效时间复杂度仅为O(n)O(n)O(n)适用于n≤1000n \le 1000n≤1000且T≤500T \le 500T≤500的输入规模。掌握此类树上组合游戏的SG\texttt{SG}SG分析法对解决类似问题有重要参考价值。