# Game of CS(LightOJ-1355)

## 题面

Jolly and Emily are two bees studying in Computer Science. Unlike other bees they are fond of playing two-player games. They used to play Tic-tac-toe, Chess etc. But now since they are in CS they invented a new game that definitely requires some knowledge of computer science.

Initially they draw a random rooted tree (a connected graph with no cycles) in a paper which consists of

nnodes, where the nodes are numbered from0ton-1and0is the root, and the edges are weighted. Initially all the edges are unmarked. And an edge weighw, haswidentical units.

Jolly has a green marker and Emily has a red marker. Emily starts the game first and they alternate turns.

In each turn, a player can color

one unitof an edge of the tree if that edge has some (at least one) uncolored units and the edge can be traversed from the root using only free edges. An edge is said to be free if the edge is not fully colored (may be uncolored or partially colored).If it’s Emily’s turn, she finds such an edge and colors one unit of it using the red marker.

If it’s Jolly’s turn, he finds such an edge and colors one unit of it with the green marker.

The player, who can’t find any edges to color, loses the game.

For example, Fig 1 shows the initial tree they have drawn. The tree contains four nodes and the weights of the edge

(0, 1), (1, 2)and(0, 3)are 1, 1 and 2 respectively. Emily starts the game. She can color any edge she wants; she colors one unit of edge(0 1)with her red marker (Fig 2). Since the weight of edge(0 1)is 1 so, this edge is fully colored.

Fig 1 Fig 2 Fig 3 Fig 4 Now it’s Jolly’s turn. He can only color one unit of edge

(0 3). He can’t color edge(1 2)since if he wants to traverse it from the root(0), he needs to use(0, 1)which is fully colored already. So, he colors one unit of edge(0 3)with his green marker (Fig 3). And now Emily has only one option and she colors the other unit of(0 3)with the red marker (Fig 4). So, both units of edge(0 3)are colored. Now it’s Jolly’s turn but he has no move left. Thus Emily wins. But if Emily would have colored edge(1 2)instead of edge(0 1), then Jolly would win. So, for this tree Emily will surely win if both of them play optimally.

## 输入

Input starts with an integer

T (≤ 500), denoting the number of test cases.Each case starts with a line containing an integer

n (2 ≤ n ≤ 1000). Each of the nextn-1lines contains two integersu v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 109)denoting that there is an edge betweenuandvand their weight isw. You can assume that the given tree is valid.

## 输出

For each case, print the case number and the name of the winner. See the samples for details.

## 样例输入

1 | 4 |

## 样例输出

1 | Case 1: Emily |

## 提示

无

## 思路

给定图，以0为根节点，每条边有一个长度，两个人轮流操作，每次为一条边上色，上一个单位长度，当一条边的颜色被涂满，则算作是减掉整段子树。判断先手是否必胜。

SG定理，对于当前节点u，每次考虑字节点v，u-v边的长度为l

当l为1时：sg(u) ^= (sg(v) + 1)

当l为奇数时： 需要判断sg(v)奇偶性，奇数-1，偶数+1；

当l为偶数时：sg(u) ^= sg(v)

## 代码

1 | vector<int> g[mxm]; |