어느 회사의 조직도는 \(N\)명의 직원으로 이루어진 트리 구조이며, 1번 직원이 회장(루트)이다. 각 직원은 한 명의 직속 상사를 가지며(회장 제외), 트리에서 어떤 직원 \(x\)의 부하 직원이란 \(x\)를 루트로 하는 부분 트리에 속한 직원들(\(x\) 자신 포함)을 말한다.

회사는 결재 라인을 점검하면서, 자신을 포함한 부하 직원의 수가 짝수인 직원이 몇 명인지 세어 보려고 한다. 그 인원수를 구하여라.

트리의 루트는 항상 1번 직원이다.

\(1 \le N \le 200{,}000\)

주어지는 그래프는 트리이다.

첫째 줄에 직원의 수 \(N\)이 주어진다.

다음 \(N-1\)개의 줄에 각각 두 정수 \(a\), \(b\) (\(1 \le a, b \le N\))가 주어지며, 직원 \(a\)와 \(b\)가 조직도 상에서 직접 연결되어 있음을 뜻한다. 주어지는 그래프는 1번을 루트로 하는 트리이다.

자신을 포함한 부하 직원의 수가 짝수인 직원의 수를 출력한다.

riseoj 작성

출처 Original