SG函数练习题：AGC017D - Game on Tree

https://atcoder.jp/contests/agc017/tasks/agc017_d

Problem Statement

There is a tree with \(N\) vertices numbered \(1, 2, ..., N\). The edges of the tree are denoted by \((x_i, y_i)\).

On this tree, Alice and Bob play a game against each other. Starting from Alice, they alternately perform the following operation:

• Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex \(1\).

A player loses the game when he/she is unable to perform the operation. Determine the winner of the game assuming that both players play optimally.

Constraints

• \(2 \leq N \leq 100000\)
• \(1 \leq x_i, y_i \leq N\)
• The given graph is a tree.

Answer

经典SG函数题。

• 只有一个端点的树的SG函数为\(0\)。
• 根只有一个儿子的树中，其SG函数是其儿子子树的SG函数+1，数学归纳法即证。
• 根有多个儿子的树中，将所有根与儿子的连边拆出来形成成一个新的树（即，对所有边\((1,u)\)，将\(u\)的子树拆出来，再在\(u\)上连一个\((1_u,u)\)），则原树SG函数等于所有拆出来的数的SG函数的异或和。

https://atcoder.jp/contests/agc017/submissions/21268298

SG函数练习题：AGC017D - Game on Tree

原文：https://www.cnblogs.com/topsecret/p/14584287.html