Informatica Online Judge

  교준이의 심부름꾼, 민제의 고충 ("Tree" Ver.) [2280 / 08E8]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 7   Total Tried : 7


The Champion of this Problem (C++) : gs17018 - ms / 761byte
My Best Submission (C++) : N/A

[]

Background

민제는 지하철 하나 없는 대한민국의 유일한 도시 청주에서 살고 있다.
현재 3009년 5월, 교준이는 청주시장이다. 교준이는 낙후된 도시, 청주를 개발하려 한다.

청주에는 1부터 $N$까지 번호가 붙은 $N$개의 군(郡)이 존재한다.
교준이는 청주에 $(N-1)$개의 양방향 도로를 설치하려 한다.
$i$번째 도로는 $A_i$번 군과 $B_i$번 군을 양방향으로 오갈 수 있도록 연결할 것이다.
$(N-1)$개의 모든 도로가 설치되었을 때, 임의의 서로 다른 두 도시에 대하여, 한 도시에서 다른 도시로 가는 이동 경로가 항상 존재함이 보장된다.
즉, 모든 도로를 설치할 경우, 청주는 하나의 트리 형태로 연결될 것이다.
현재 청주는, 어떠한 도로도 설치되어 있지 않음에 유의하라.

하지만, 청주에는 충분한 예산이 없다.
고로 $(N-1)$개의 도로 설치 계획 중 정확하게 $k$개의 계획만 이행하려고 한다.
즉, 교준이가 민제에게 "$k$개의 도로를 설치해라."라고 명령하면, 민제는 $(N-1)$개의 도로 중 정확히 $k$개만 선택하여, 실제로 설치한다.
결과적으로 청주는 $(N-k)$개의 트리 형태로 연결될 것이다.
이 때, 모든 $(N-k)$개의 트리가 포함하는 군(郡)의 개수가 전부 같다면, 민제는 이를 "사회주의적 개발"이라고 부른다.
$k$의 값이 같아도, 민제가 어떤 $k$개의 도로를 선택하냐에 따라, "사회주의적 개발"이 될 수도, 되지 않을 수도 있음에 유의하라.

교준이는 궁금증이 생겼다:
"민제가 사회주의적 개발을 할 수 있도록, $k$개의 도로를 선택하는 방법이 존재하는, 그런 자연수 $k$는 무엇이 있을까?"

교준이의 영원한 심부름꾼, 민제는 오늘도 교준이의 궁금증을 해결해주어야 한다.
허나 민제는 "1+9+10=19"라고 말할 정도로 수학을 못하는 바보다.
민제를 위하여 교준이의 질문에 답해주는 프로그램을 작성해보자!

Input

첫 번째 줄에는 청주의 군의 개수를 나타내는 자연수 $N$이 주어진다.

두 번째 줄부터 $(N-1)$개의 줄에 걸쳐 $(N-1)$개의 도로에 관한 정보가 주어진다.

$(i+1)$번째 줄에는 두 자연수 $A_i$, $B_i$가 사이에 공백을 두고 주어진다($1 ≤ i < N$).

[입력값의 정의역]

$2 ≤ N ≤ 10^6$
$1 ≤ A_i ≤ N$ ($1 ≤ i < N$)
$1 ≤ B_i ≤ N$ ($1 ≤ i < N$)
$A_i ≠ B_i$ ($1 ≤ i < N$)

Output

"민제가 사회주의적 개발을 할 수 있도록, $k$개의 도로를 선택하는 방법이 존재하는, 그런 자연수 $k$들"의 집합을 ${K_1, ..., K_T}$라 하자.
(단, $1 ≤ K_1 < ... < K_T < N$.)

첫 번째 줄에는 자연수 $T$의 값을 출력한다.
두 번째 줄에는 $∑(K_i ⊕ i) = (K_1 ⊕ 1) + ... + (K_T ⊕ T)$의 값을 출력한다.
여기서 ⊕는 배타적 논리합을 나타내는 기호다.

IO Example

입력
8
1 2
2 3
2 4
2 5
5 6
5 7
7 8

출력
2
12

보충 설명
[사진]
$k = 6$, $k = 7$일 때만 가능하다.
$K_1 = 6$, $K_2 = 7$이므로, 두 번째 줄에 $∑(K_i ⊕ i) = (6 ⊕ 1) + (7 ⊕ 2) = 7 + 5 = 12$를 출력하여야 한다.

Hint
$K_i$의 값을 정확히 알아야 할 필요가 있는가.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]