提出 #10679447

---

ソースコード 拡げる

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N+1)
stack = [1]
dist[1] = 0
while stack:
    v = stack.pop()
    for w in graph[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            stack.append(w)

ev = [i for i,x in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for i,x in enumerate(dist) if x % 2 == 1 and i > 0]

def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
    assert len(ev) == x0 + x1 + x2
    assert len(od) == y0 + y1 + y2
    P = [0] * (N+1)
    for i in ev:
        if x0:
            P[i] = (x0 + y0) * 3
            x0 -= 1
            continue
        if x1:
            P[i] = (x1 + y1) * 3 - 2
            x1 -= 1
            continue
        if x2:
            P[i] = (x2 + y2) * 3 - 1
            x2 -= 1
            continue
    for i in od:
        if y0:
            P[i] = (x0 + y0) * 3
            y0 -= 1
            continue
        if y1:
            P[i] = (x1 + y1) * 3 - 2
            y1 -= 1
            continue
        if y2:
            P[i] = (x2 + y2) * 3 - 1
            y2 -= 1
            continue
    return P[1:]

def solve(N, ev, od):
    x0 = N // 3
    x1 = (N+2) // 3
    x2 = (N+1) // 3
    perm = [0] * (N+1)
    LE = len(ev)
    LO = len(od)
    if LE <= x0:
        return make_perm(N, ev, od, LE, 0, 0, x0-LE, x1, x2)
    if LO <= x0:
        return make_perm(N, ev, od, x0-LO, x1, x2, LO, 0, 0)
    if LE == x1:
        return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
    if LO == x1:
        return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
    # どちらも x1 よりたくさんある
    return make_perm(N, ev, od, LE-x1, x1, 0, LO-x2, 0, x2)

P = solve(N, ev, od)
print(' '.join(map(str, P)))

提出情報

ジャッジ結果