Under construction

Still being built. Things may change

Full Binary Tree

Time limit5sMemory limit512 MB

Summary
Given a tree with up to 15 nodes, delete as few nodes as possible so the remaining nodes form a full binary tree for some choice of root.
Level

Medium5 of 10

Topics
Tree, Dynamic programming, Brute force
Solved
No attempts yet

Problem

A tree is a connected graph with no cycles.

A rooted tree is a tree in which one vertex is chosen as the root. In a rooted tree, if XX and YY are joined by an edge and the shortest path from the root to XX is shorter than the shortest path from the root to YY, then YY is a child of XX.

A full binary tree is a rooted tree in which every node has exactly 22 children or 00 children.

You are given a tree GG with NN nodes, numbered from 11 to NN. You may delete some of the nodes. Deleting a node also deletes every edge attached to it. Delete as few nodes as possible so that the remaining nodes form a full binary tree for some choice of root among them.

Input

The first line contains the number of test cases TT. TT test cases follow. The first line of each test case contains the number of nodes NN. Each of the next N−1N-1 lines contains two space separated integers XiX_i and YiY_i, meaning that GG has an undirected edge between XiX_i and YiY_i.

Limits

  • 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
  • The edges of each test case always form a connected tree.

Output

For each test case, print one line in the form Case #x: y, where xx is the test case number starting from 11 and yy is the minimum number of nodes to delete from GG to make a full binary tree.

Hint

In the first sample test case, GG is already a full binary tree with node 11 as the root, so nothing has to be deleted.

In the second test case, deleting nodes 33 and 77 leaves a full binary tree rooted at node 22.

In the third test case, deleting node 11 leaves a full binary tree rooted at node 33. Deleting node 44 and rooting at node 22 works as well.

Examples3

  1. Example 1

    Input
    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
    Expected output
    Case #1: 0
Case #2: 2
Case #3: 1

  2. Example 2

    Input
    3
2
1 2
2
2 1
3
1 2
2 3
    Expected output
    Case #1: 1
Case #2: 1
Case #3: 0

  3. Example 3

    Input
    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
    Expected output
    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