Submission #60827057

---

Source Code Expand

N = int(input())
T = [[] for _ in range(N)]
deg = [0] * N
for _ in range(N - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    T[u].append(v)
    T[v].append(u)
    deg[u] += 1
    deg[v] += 1
ans = N
for u in range(N):
    T[u].sort(key=lambda v: -deg[v])
    x = y = 0
    for v in T[u]:
        x += 1
        y = deg[v] - 1
        ans = min(ans, N - (1 + x + x * y))
print(ans)

Submission Info

Judge Result