Submission #55347016

---

Source Code Expand

import sys

input = sys.stdin.readline


def find_centroid(T):
    N = len(T)
    size = [1] * N
    st = [(0, 0, 0)]
    while st:
        v, p, t = st.pop()
        if t == 0:
            st.append((v, p, 1))
            for c in T[v]:
                if c != p:
                    st.append((c, v, 0))
        else:
            is_centroid = True
            for c in T[v]:
                if c != p:
                    size[v] += size[c]
                    if size[c] > N // 2:
                        is_centroid = False
            if is_centroid and N - size[v] <= N // 2:
                return v


N = int(input())
T = [[] for _ in range(N)]
for i in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    T[u].append(v)
    T[v].append(u)
g = find_centroid(T)
comp = [[] for _ in range(N)]
st = []
for v in T[g]:
    st.append((v, g, v))
while st:
    v, p, i = st.pop()
    comp[i].append(v)
    for c in T[v]:
        if c != p:
            st.append((c, v, i))

vs = []
for i in range(N):
    vs += comp[i]
if N % 2 == 0:
    vs.append(g)

for i in range(N // 2):
    print(vs[i] + 1, vs[i + N // 2] + 1)

Submission Info

Judge Result