ICPC Southeastern Europe Contest 2019 D Game on a Tree

Game on a Tree Alice and Bob play a game on a tree. Initially, all nodes are white.
Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In each turn, a player moves the chip from the current position to an ancestor or descendant node, as long as the node is not black. This node also becomes black. The player who cannot move the chip looses.
Who wins the game?
An ancestor of a node v in a rooted tree is any node on the path between v and the root of the tree.
A descendant of a node v in a rooted tree is any node w such that node v is located on the path between w and the root of the tree.
We consider that the root of the tree is 1.
Input
The first line contains one integer n (1≤n≤100000)n(1≤n≤100000) — the number of nodes.Each of the next n−1n−1 lines contains two integers uu and vv (1≤u,v≤n)(1≤u,v≤n) — the edges of the tree. It is guaranteed that they form a tree.
Output
In a single line, print “Alice” (without quotes), if Alice wins. Otherwise, print “Bob”.
출력 시 줄 끝의 여분의 공백은 답안의 정확성에 영향을 주지 않습니다

샘플 입력 1

4
1 2
2 3
3 4

샘플 출력 1

Bob

샘플 입력 2

7
2 1
2 6
1 3
2 5
7 2
2 4

샘플 출력 2

Alice

문제 해결 방법:
제목에서 알 수 있듯이 이 게임은 한 사람이 한 걸음 걷고 현재 위치에서만 이동할 수 있다. 그러면 우리는 두 개의 점을 매칭하는 것을 고려할 수 있다.
우리는 n개의 점이 있다고 가정하면 이 몇 개의 점을 n/2조로 나누고 두 개가 일치하면 집합**{(p1,p2),(p3,p4),...(pn-1,pn+1)}**를 얻을 수 있음을 고려할 수 있다.
첫 번째 시나리오:
만약에 모든 점이 완벽하게 일치한다면 우리는 선손이 한 걸음 한 걸음 가면 후손이 그와 일치하는 점만 갈 수 있다. 그러면 가장 큰 일치는 완벽하게 일치하는 상황에서 후수가 반드시 이긴다. 즉, B가 반드시 이긴다.
두 번째 시나리오:
이 그림의 최대 매칭이 완벽하게 매칭되지 않으면 매칭이 불가능하다(점 사이에 연결이 없다). 만약에 선수가 매칭 안에 없는 점을 선택하면 선수가 반드시 이길 수 있다. 즉, A가 반드시 이길 수 있다.
여기를 고려한 후 이 그림의 최대 일치수가 완벽하게 일치하는지 확인하면 이 문제를 해결할 수 있다.dfs를 사용하면 이 그림의 완벽한 일치수를 찾을 수 있습니다.
여기에 우리는 dfs를 진행하기 위해 수조s[]를 설정한다. s[i]는 i를 뿌리 노드로 하는 자수에 남은 일치하지 않는 노드의 개수를 나타낸다. 그러면 우리는 잎 노드에서 욕심을 내고 위로 일치하면 된다.
AC 코드:

#include
#include
#include
#include
#include
#include
#include