[UCPC][2019][예선] D번 풀이

풀이

주어지는 간선의 위치를 받아서 어떤 노드와 어떤 노드가 연결되었는지 트리로 표현합니다. 모든 leaf 노드가 root까지 도달하기 위한 깊이들의 합이 홀수이면 먼저 시작하는 사람이 이기고, 짝수이면 뒤에 시작하는 사람이 이깁니다. 깊이를 찾는 방법은 Tree포스팅을 참고합니다.

코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n;
bool check[500001];
vector<int> v[500001];
queue<int> q;
int a, b;
long long depth[500001];
long long ans = 0;

/*void bfs(int s) {
	
	q.push(s);
	while (!q.empty()) {
		bool isLeaf = true;
		int x = q.front(); q.pop();
		printf("방문 %d\n", x);
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (check[y] == false) {
				isLeaf = false;
				check[y] = true;
				depth[y] = depth[x] + 1;
				q.push(y);
			}
		}
		if (isLeaf) {
			printf("%d는 leaf!\n", x);
		}
	}
}*/

void dfs(int s) {
	bool isLeaf = true;
	if (check[s] == true) return;
	else {
		check[s] = true;
	}
	for (int i = 0; i < v[s].size(); i++) {
		int y = v[s][i];
		if (check[y] == false) {
			isLeaf = false;
			depth[y] = depth[s] + 1;
			dfs(y);
		}
	}
	if (isLeaf) {
		ans += depth[s];
	}
}


int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++) {
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	depth[1] = 0;
	dfs(1);
	
	if (ans % 2 == 1) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}