61 lines
1.4 KiB
Python
61 lines
1.4 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
def min_remove(D):
|
||
|
|
m = len(D)
|
||
|
|
for k in range(1, len(D)):
|
||
|
|
BT = []
|
||
|
|
V = [None] * len(D)
|
||
|
|
r = len(D) - 1 - max_edges(D, BT, V, k)
|
||
|
|
if m is None or r < m:
|
||
|
|
m = r
|
||
|
|
return m
|
||
|
|
|
||
|
|
|
||
|
|
def max_edges(D, BT, V, k):
|
||
|
|
if V[k] is None:
|
||
|
|
BT.append(k)
|
||
|
|
if len(D[k]) <= 1: # Either one edge (parent) or two (parent and one child)
|
||
|
|
BT.remove(k)
|
||
|
|
V[k] = 1
|
||
|
|
else:
|
||
|
|
m1 = None
|
||
|
|
m2 = None
|
||
|
|
for e in D[k]:
|
||
|
|
if e in BT:
|
||
|
|
continue
|
||
|
|
d = max_edges(D, BT, V, e)
|
||
|
|
if m1 is None or d > m1:
|
||
|
|
m2 = m1
|
||
|
|
m1 = d
|
||
|
|
elif m2 is None or d > m2:
|
||
|
|
m2 = d
|
||
|
|
BT.remove(k)
|
||
|
|
if m2 is None:
|
||
|
|
V[k] = 1
|
||
|
|
else:
|
||
|
|
V[k] = 1 + m1 + m2
|
||
|
|
return V[k]
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
t = int(input())
|
||
|
|
for i in range(1, t+1):
|
||
|
|
n = int(input())
|
||
|
|
D = [None] * (n+1)
|
||
|
|
for j in range(n-1):
|
||
|
|
string = input().split(' ')
|
||
|
|
a, b = int(string[0]), int(string[1])
|
||
|
|
|
||
|
|
if D[a] is None:
|
||
|
|
D[a] = [b]
|
||
|
|
else:
|
||
|
|
D[a].append(b)
|
||
|
|
|
||
|
|
if D[b] is None:
|
||
|
|
D[b] = [a]
|
||
|
|
else:
|
||
|
|
D[b].append(a)
|
||
|
|
|
||
|
|
print("Case #" + str(i) + ": " + str(min_remove(D)))
|
||
|
|
|