문제 이해

Leaf Node로부터 Root Node로 순서를 번갈아가며 2명이 말을 움직인다.
Root Node에 도착하면 게임 말은 없어진다.
만약 움직일 말이 없으면 그 턴에 말을 움직여야 하는 사람은 지게 된다.

A가 먼저 말을 움직일 경우, A가 이 게임을 이길 수 있는지 없는지를 확인하는 문제이다.

---

문제 풀이

문제는 복잡하지만 생각보다 풀이는 간단하다.
Root ~ Leaf Node 까지의 Edge 개수가 짝수라고 가정하자.
그렇다면 먼저 움직인 사람이 질 것이다

• 증명
  n = 2일 때 : A가 움직이고 B가 움직이면 말이 없어지므로 A가 짐
  n = 2k일 때 A가 진다고 가정하자.
  n = 2(k+1)일 때를 살펴보자면, n=2k일 때 A가 지기 때문에 A = 2k + 1일 때 A가 움직일 턴이라고 생각할 수 있다. 즉, A가 2k+1 순번 때 움직이고, B가 2k+2 순번 때 움직이면
  2k+3 순번인 A는 움직일 말이 없다. 따라서 A가 진다.
  즉, 수학적 귀납법에 의해 A가 진다.

반대로 Root ~ Leaf Node까지의 Edge가 홀수일 경우 먼저 움직인 사람이 이길 것이다.

어떤 말을 움직여도 되기 때문에, 가장 쉽게 Leaf Node M에 놓여 있는 말이 없어질 때 까지 움직이고, 이후 Leaf Node N에 놓인 말을 움직이는 방식으로 게임을 진행해보자. 이 경우, (Root ~ M 거리) + (Root ~ N 거리)의 길이를 가진 Leaf Node에서 말 한개를 움직이는 것과 같은 효과를 보인다.

따라서, 모든 Leaf Node에 대하여 Root Node까지의 거리를 합하고, 이 값이 짝수인지 홀수인지를 따져보면 될 것이다

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static ArrayList<Integer>[] nodes;
	static int N;
	static boolean[] visit;
	static int ans = 0;
	
	static void find_leaf(int node, int length) { 
    // length : Root ~ (매개변수) node까지의 거리
		visit[node] = true;
		
		boolean leaf = true;
		for(int s:nodes[node]) {
			if(!visit[s]) { // 부모 Node와 연결된 간선이 아닐 경우 실행된다
				leaf = false;
				find_leaf(s, length+1); 
			}
		}
		
		if(leaf) ans+=length;
        // leaf = true -> if(!visit[s])를 만나지 않았다
        // 즉, 연결된 간선이 이미 방문 되었던 간선이라는 의미이므로, 
        // 부모 Node만 연결되었다는 의미이다.
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		nodes = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for(int i =1;i<N+1;i++) {
			nodes[i] = new ArrayList<>();
		}
		
		for(int i =0;i<N-1;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			nodes[tmp1].add(tmp2);
			nodes[tmp2].add(tmp1);
		}
		
		find_leaf(1, 0);
        // 트리의 간선이 주어질 뿐, Root Node가 무엇인지는 주어지지 않았다.
        // 다행히 이 트리는 무방향 그래프이므로, 모든 Node가 Root가 될 수 있다.
        // 나는 1을 Root로 두었다.
		
		if(ans%2==0) System.out.println("No"); 
        // 짝수일 경우 무조건 (A가) 짐
		else System.out.println("Yes"); 
        // 홀수일 경우 무조건 (B가) 짐
	}

	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 : 디버깅 때 사용했던 출력 문구를 지우지 않아 틀렸다.