题目描述

Jolly\texttt{Jolly}Jolly和Emily\texttt{Emily}Emily在纸上画了一棵有根树，结点编号为000到n−1n - 1n−1，000为根。每条边带有权值www，表示该边有www个相同的单位。初始时所有边均未涂色。
游戏规则如下：

1. Emily\texttt{Emily}Emily先手，双方轮流操作。
2. 每轮玩家可以选择一条边，该边至少有一个单位尚未涂色，并且从根结点出发仅通过空闲边（即尚未被完全涂色的边）可以到达该边。
3. Emily\texttt{Emily}Emily用红色涂一个单位，Jolly\texttt{Jolly}Jolly用绿色涂一个单位。
4. 无法找到可涂边的玩家输掉游戏。

给定树的结构和边权，双方均采取最优策略，求获胜者。

输入格式

第一行一个整数TTT（T≤500T \le 500T≤500），表示测试用例数。
每个测试用例第一行一个整数nnn（2≤n≤10002 \le n \le 10002≤n≤1000）。
接下来n−1n - 1n−1行，每行三个整数uuu、vvv、www（0≤u,v<n0 \le u, v < n0≤u,v<n，u≠vu \ne vu=v，1≤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-Grundy（SG\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共同决定。

通过归纳分析可得如下结论：

• 若w=1w = 1w=1，则该边只有一个单位，必须等所有子博弈结束后才能涂这最后一个单位，相当于在子博弈的SG\text{SG}SG值CCC基础上再增加一步，因此g(u)=C+1g(u) = C + 1g(u)=C+1。
• 若www为偶数，则该边的涂色操作不会改变子博弈的奇偶性，整体SG\texttt{SG}SG值不变，即g(u)=Cg(u) = Cg(u)=C。
• 若www为奇数且w>1w > 1w>1，则每次在该边上涂色都会翻转子博弈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必胜。

算法步骤：

1. 以000为根，通过DFS\texttt{DFS}DFS遍历树，建立父子关系。
2. 对于每个结点uuu，递归计算其所有子结点vvv的g(v)g(v)g(v)，并求异或和CCC。
3. 若uuu不是根，则根据父边权值www计算g(u)g(u)g(u)；若uuu是根，则直接将CCC作为整棵树的SG\texttt{SG}SG值。
4. 若整棵树的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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;llsgFunc(ll w,ll c){if(w==1)returnc+1;if(w%2==0)returnc;returnc^1;}voiddfs(intu,intparent,ll parentWeight,vector<vector<pair<int,ll>>>&adj,vector<ll>&sg,ll&totalXor){ll childXor=0;for(auto&e:adj[u]){intv=e.first;ll w=e.second;if(v==parent)continue;dfs(v,u,w,adj,sg,totalXor);childXor^=sg[v];}if(u==0){totalXor=childXor;sg[0]=childXor;}else{sg[u]=sgFunc(parentWeight,childXor);}}intmain(){intT;scanf("%d",&T);for(intcaseNo=1;caseNo<=T;++caseNo){intn;scanf("%d",&n);vector<vector<pair<int,ll>>>adj(n);for(inti=0;i<n-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});}vector<ll>sg(n,0);ll totalXor=0;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、偶数、奇数>1>1>1）并推导出对应的SG\texttt{SG}SG值公式。
• 使用深度优先遍历自底向上计算，避免指数级状态。

该解法简洁高效，时间复杂度仅为O(n)O(n)O(n)，适用于n≤1000n \le 1000n≤1000且T≤500T \le 500T≤500的输入规模。掌握此类树上组合游戏的SG\texttt{SG}SG分析法，对解决类似问题有重要参考价值。