이번 문제는 깊이우선탐색을 통해 해결하였다. 이번 문제는 인접 리스트 방식으로 그래프를 구성하였다. 이 문제의 패턴을 살펴보면 리프 노드에서 루트 노드까지의 거리들의 합이 짝수일 경우에는 No가 출력되고 합이 홀수일 경우에는 Yes가 출력된다. 그러므로 루트 노드인 1부터 시작하여 깊이 우선으로 탐색을 해가며 루트노드로부터 각각 노드의 거리를 모두 구하고 마지막에 리프 노드인 것들의 거리의 합을 구하면 문제를 해결할 수 있다. 문제를 제출하는 과정에서 시간 초과 이슈가 발생하였고 이를 개선하기 위해 sys.stdin.readline을 사용하여 입력 받고, PyPy3로 제출하였다.

• input을 sys.stdin.readline으로 대입한다.
• 재귀 제한을 늘린다.
• dfs함수를 cur을 인자로 갖도록 선언한다.
  -> visited[cur]를 True로 변경한다.
  -> tree[cur]을 순회하는 next에 대한 for문을 돌린다.
  --> 만약 visited[next]가 False일 경우,
  ---> dist[next]를 dist[cur]+1로 갱신한다.
  ---> dfs(next)를 재귀호출한다.
• n을 입력받는다.
• 트리에 해당하는 리스트 tree를 빈 리스트 n+1개로 선언한다. (인접 리스트 방식으로 저장하기 위함)
• 방문처리에 사용할 리스트 visited를 False n+1개로 채운다.
• 각 노드의 거리를 저장할 리스트 dist를 0 n+1개로 채운다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• n-1번 반복하는 for문을 돌린다.
  -> 임시변수 a, b를 입력받는다.
  -> tree[a]에 b를 넣는다.
  -> tree[b]에 a를 넣는다.
• dfs(1)을 호출한다.
• 2부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 tree[i]의 길이가 1일 경우(리프 노드일 경우), answer에 dist[i]를 더한다.
• 만약 answer가 짝수라면 No를 출력한다.
• 만약 answer가 홀수라면 Yes를 출력한다.

Code

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def dfs(cur):
    visited[cur]=True
    for next in tree[cur]:
        if visited[next]==False:
            dist[next]=dist[cur]+1
            dfs(next)
n=int(input())
tree=[[] for _ in range(n+1)]
visited=[False for _ in range(n+1)]
dist=[0 for _ in range(n+1)]
answer=0
for _ in range(n-1):
     a, b=map(int, input().split())
     tree[a].append(b)
     tree[b].append(a)
dfs(1)
for i in range(2, n+1):
    if len(tree[i])==1:
        answer+=dist[i]
if answer%2==0:
    print('No')
else:
    print('Yes')