만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

정 이진 트리 만들기

시간 제한5초메모리 제한512 MB

요약
최대 15개 정점으로 이루어진 트리에서 정점을 최소로 삭제해 남은 정점이 완전 이진 트리를 이루게 합니다.
난이도

보통10점 중 5점

유형
트리, 동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

트리는 사이클이 없는 연결 그래프이다.

루트 있는 트리는 정점 하나를 루트로 정한 트리이다. 루트 있는 트리에서 XX와 YY가 간선으로 이어져 있고 루트에서 XX까지의 최단 경로가 루트에서 YY까지의 최단 경로보다 짧으면, YY를 XX의 자식이라고 한다.

정 이진 트리는 모든 노드의 자식 수가 정확히 22개이거나 00개인 루트 있는 트리이다.

노드가 NN개인 트리 GG가 주어진다. 노드에는 11번부터 NN번까지 번호가 붙어 있다. 노드를 몇 개 지울 수 있고, 노드를 지우면 그 노드에 붙은 간선도 함께 지워진다. 남은 노드 중에서 루트를 하나 고르면 정 이진 트리가 되도록, 지우는 노드 수를 최소로 하라.

입력

첫 줄에 테스트 케이스 수 TT가 주어진다. 이어서 테스트 케이스가 TT개 주어진다. 각 테스트 케이스의 첫 줄에는 트리의 노드 수 NN이 주어진다. 다음 N−1N-1개 줄에는 공백으로 구분된 두 정수 XiX_i와 YiY_i가 주어지며, GG에 XiX_i와 YiY_i를 잇는 무방향 간선이 있다는 뜻이다.

제한

  • 1≤T≤1001 \le T \le 100
  • 2≤N≤152 \le N \le 15
  • 1≤Xi,Yi≤N1 \le X_i, Y_i \le N
  • 각 테스트 케이스의 간선은 항상 연결된 트리를 이룬다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 11부터 시작하는 테스트 케이스 번호이고, yy는 GG를 정 이진 트리로 만들기 위해 지워야 하는 노드 수의 최솟값이다.

힌트

예제의 첫 번째 테스트 케이스에서 GG는 11번 노드를 루트로 보면 이미 정 이진 트리이므로 아무것도 지우지 않아도 된다.

두 번째 테스트 케이스에서는 33번과 77번 노드를 지우면 22번 노드가 루트인 정 이진 트리가 된다.

세 번째 테스트 케이스에서는 11번 노드를 지우면 33번 노드가 루트인 정 이진 트리가 된다. 44번 노드를 지우고 22번 노드를 루트로 삼아도 된다.

예제3

  1. 예제 1

    입력
    3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4
    예상 출력
    Case #1: 0
Case #2: 2
Case #3: 1

  2. 예제 2

    입력
    3
2
1 2
2
2 1
3
1 2
2 3
    예상 출력
    Case #1: 1
Case #2: 1
Case #3: 0

  3. 예제 3

    입력
    100
15
8 1
3 2
14 9
14 13
4 9
4 7
5 8
12 9
10 6
9 8
6 5
11 4
8 15
8 2
6
4 1
5 2
3 1
1 2
6 2
10
3 4
9 6
4 10
10 2
1 9
6 8
3 7
4 6
5 6
12
4 3
11 8
1 6
10 1
6 4
12 9
4 8
5 2
12 7
2 9
12 4
5
1 5
3 2
1 4
4 3
11
6 2
2 1
8 9
7 4
11 3
6 10
8 4
9 2
11 5
8 11
4
4 1
2 3
4 2
8
6 4
4 7
2 6
8 1
5 3
8 3
1 4
12
6 3
12 7
3 10
9 12
3 5
10 2
7 11
10 8
7 1
10 9
4 12
10
3 9
1 3
6 8
2 3
7 3
10 6
3 4
9 5
5 6
3
2 1
3 2
11
10 7
8 9
3 5
2 4
5 8
10 8
9 6
9 2
1 5
3 11
14
4 3
5 13
1 8
3 10
7 13
12 9
14 5
13 11
12 1
3 2
13 2
3 9
2 6
5
2 3
5 2
3 4
3 1
8
7 5
2 8
2 4
7 2
2 6
1 4
3 4
9
1 8
3 8
2 4
8 7
8 5
4 6
5 4
9 2
7
5 6
4 1
7 1
2 7
6 7
6 3
9
2 1
2 8
7 3
6 1
4 9
9 3
2 3
4 5
3
1 3
3 2
4
2 3
4 1
2 4
8
3 4
6 8
5 2
6 3
3 1
4 2
6 7
10
7 9
7 6
5 1
3 9
4 1
2 10
1 10
1 3
8 10
5
1 3
3 2
5 3
4 3
9
4 6
1 7
8 5
3 6
5 7
7 9
6 5
5 2
3
1 2
1 3
3
2 1
2 3
8
2 6
8 3
8 5
6 1
7 6
6 3
4 3
10
1 6
9 8
10 5
2 7
8 4
10 1
4 1
10 7
1 3
7
5 3
3 1
6 3
7 4
7 6
2 5
2
2 1
6
2 5
4 3
5 1
1 6
3 2
3
1 2
1 3
11
4 10
10 1
1 5
8 6
7 4
10 11
9 6
10 3
2 6
1 2
2
2 1
3
3 2
1 3
6
2 4
1 3
2 3
4 6
3 5
2
2 1
8
7 2
2 1
8 1
6 1
8 5
4 1
3 2
8
4 5
3 1
4 7
3 4
5 2
6 2
3 8
13
6 8
7 10
4 2
7 12
1 3
13 1
13 7
8 5
9 6
6 1
1 2
11 13
11
5 9
8 3
1 7
8 6
11 5
9 8
9 1
10 4
2 6
10 2
15
6 13
6 7
9 14
14 5
12 9
6 8
1 14
15 10
13 4
12 2
15 3
11 5
7 5
5 10
4
2 4
1 4
3 2
3
1 2
3 2
9
8 3
3 9
9 6
9 1
2 7
4 9
5 1
5 2
13
1 3
9 11
4 6
3 4
5 12
7 8
9 10
7 12
7 13
13 3
1 2
13 10
8
5 3
8 3
7 3
8 1
2 8
6 7
8 4
14
9 11
2 11
8 5
8 12
12 7
6 5
10 2
2 8
8 14
13 3
4 1
13 4
13 8
15
10 4
14 4
3 12
1 13
5 15
4 9
1 3
5 4
8 1
11 3
6 1
12 4
14 7
10 2
7
1 6
5 4
3 6
5 3
7 3
2 3
7
5 6
7 6
1 4
4 6
3 5
2 3
7
7 4
5 2
6 1
3 2
1 5
7 5
12
2 9
7 1
5 3
4 10
5 1
9 6
2 8
4 8
1 4
12 11
12 4
9
9 2
3 7
6 5
7 6
6 9
6 4
8 4
6 1
10
9 3
5 3
1 3
9 2
6 7
8 3
9 4
7 9
10 4
2
1 2
10
6 10
7 6
1 7
1 8
2 7
3 2
9 3
4 9
5 7
15
2 3
8 12
13 8
15 5
4 7
2 14
10 9
11 7
1 14
6 12
7 10
10 12
1 12
15 6
13
10 1
4 9
5 10
3 9
8 10
9 12
13 8
7 8
2 12
8 6
11 5
12 8
2
2 1
2
2 1
12
4 8
9 5
9 12
7 4
4 3
2 11
6 12
8 2
10 2
9 2
1 8
9
4 1
3 7
5 4
8 9
6 3
2 1
3 1
9 3
8
1 8
5 4
8 6
7 4
7 6
2 6
8 3
11
9 10
1 8
1 4
1 5
1 9
3 7
6 3
11 9
2 3
4 7
4
2 4
1 3
4 1
3
3 2
3 1
7
5 2
3 6
2 1
5 7
3 4
4 7
15
15 1
11 3
2 4
9 15
2 15
13 5
10 11
10 15
7 8
9 14
2 5
6 15
12 11
15 8
13
4 13
5 11
3 1
1 11
1 6
9 10
12 7
8 12
13 11
11 10
13 8
13 2
12
6 4
5 12
3 9
4 11
8 7
1 9
9 4
2 4
8 11
12 10
9 12
6
3 6
4 3
2 4
5 2
1 2
12
12 6
10 1
7 8
8 11
8 10
9 7
1 3
6 2
5 7
4 12
1 2
8
3 1
5 3
5 8
6 3
4 3
7 4
2 3
9
7 9
1 4
5 4
6 2
9 3
2 8
5 7
2 7
10
5 9
7 5
2 8
5 6
10 3
8 9
9 1
3 9
4 8
6
2 4
1 3
3 4
5 3
6 1
5
3 1
2 3
4 3
5 3
11
5 1
10 8
10 6
11 10
9 3
3 7
2 9
4 1
1 11
3 1
4
1 2
1 4
3 4
6
6 2
2 3
1 2
4 1
5 1
12
11 8
10 9
4 8
10 7
12 1
8 10
8 12
4 3
12 5
11 6
11 2
15
7 2
4 15
4 2
10 2
11 15
13 4
5 11
5 14
8 15
15 1
2 6
4 3
9 1
9 12
9
9 6
3 4
8 5
6 4
7 2
8 6
3 7
1 2
12
4 9
10 1
5 7
9 12
11 6
8 2
4 1
4 7
2 3
8 1
10 11
8
1 3
8 5
4 6
2 5
7 6
2 1
5 7
14
14 6
13 11
2 13
11 8
6 9
10 12
1 13
5 10
10 4
6 8
6 3
10 11
7 8
15
4 3
9 5
2 15
6 10
12 7
14 7
8 2
7 13
2 12
11 7
10 2
6 1
3 15
7 9
8
6 1
1 8
4 7
1 7
2 5
2 1
7 3
8
4 3
8 7
2 1
5 6
4 5
1 6
4 7
5
5 4
5 2
5 3
1 5
2
1 2
5
1 5
5 2
5 3
1 4
11
6 4
2 8
11 7
10 9
5 10
6 11
3 7
1 5
11 10
8 7
7
4 2
6 1
5 7
1 5
7 4
4 3
10
1 4
3 4
3 10
2 6
8 6
4 8
5 7
8 7
9 7
15
15 13
7 15
15 11
11 10
4 5
3 9
4 12
3 14
12 11
9 8
11 9
2 3
1 12
1 6
2
2 1
9
8 9
3 7
4 7
1 4
8 2
5 9
4 6
3 5
7
7 3
3 5
1 7
6 3
4 2
2 3
    예상 출력
    Case #1: 6
Case #2: 1
Case #3: 3
Case #4: 5
Case #5: 2
Case #6: 2
Case #7: 1
Case #8: 3
Case #9: 1
Case #10: 5
Case #11: 0
Case #12: 2
Case #13: 5
Case #14: 0
Case #15: 1
Case #16: 2
Case #17: 0
Case #18: 2
Case #19: 0
Case #20: 1
Case #21: 1
Case #22: 3
Case #23: 2
Case #24: 2
Case #25: 0
Case #26: 0
Case #27: 1
Case #28: 3
Case #29: 2
Case #30: 1
Case #31: 3
Case #32: 0
Case #33: 2
Case #34: 1
Case #35: 0
Case #36: 1
Case #37: 1
Case #38: 1
Case #39: 1
Case #40: 2
Case #41: 4
Case #42: 6
Case #43: 1
Case #44: 0
Case #45: 4
Case #46: 4
Case #47: 1
Case #48: 5
Case #49: 6
Case #50: 2
Case #51: 2
Case #52: 2
Case #53: 5
Case #54: 4
Case #55: 3
Case #56: 1
Case #57: 5
Case #58: 6
Case #59: 2
Case #60: 1
Case #61: 1
Case #62: 1
Case #63: 2
Case #64: 1
Case #65: 4
Case #66: 1
Case #67: 0
Case #68: 4
Case #69: 6
Case #70: 4
Case #71: 3
Case #72: 1
Case #73: 3
Case #74: 3
Case #75: 2
Case #76: 1
Case #77: 1
Case #78: 2
Case #79: 2
Case #80: 1
Case #81: 1
Case #82: 3
Case #83: 6
Case #84: 4
Case #85: 5
Case #86: 3
Case #87: 3
Case #88: 8
Case #89: 1
Case #90: 3
Case #91: 2
Case #92: 1
Case #93: 0
Case #94: 2
Case #95: 2
Case #96: 1
Case #97: 2
Case #98: 1
Case #99: 4
Case #100: 2