提出 #76915569

ソースコード 拡げる

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())

graph = [[] for n in range(N + 1)]

for n in range(N - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


res = 0

from_one = [-1] * (N + 1)

from collections import deque

queue = deque()

queue.append((1, 0))

from_one[1] = 0

while queue:
    q = queue.popleft()
    now = q[0]
    c = q[1]

    for neibor in graph[now]:
        if from_one[neibor] != -1:
            continue
        from_one[neibor] = c + 1
        queue.append((neibor, c + 1))

# print(from_one)


counts = [0] * (N + 1)


def dfs(now, pre):
    c = 0
    for neibor in graph[now]:
        if neibor == pre:
            continue
        else:
            c += dfs(neibor, now)
    counts[now] = c + 1
    return c + 1


dfs(1, 0)
# print(counts)

res = [0] * (N + 1)
res[1] = sum(from_one) + 1
# print(res)


queue = deque()
queue.append((1, res[1]))
while queue:
    q = queue.popleft()
    now = q[0]
    c = q[1]
    for neibor in graph[now]:
        if res[neibor] != 0:
            continue
        res[neibor] = c + N - 2 * counts[neibor]
        queue.append((neibor, c + N - 2 * counts[neibor]))

# print(res)

for n in range(1, N + 1):
    print(res[n])

提出情報

提出日時
問題 I - Distance Sums 2
ユーザ kurome_rome
言語 Python (PyPy 3.11-v7.3.20)
得点 500
コード長 1312 Byte
結果 AC
実行時間 1002 ms
メモリ 361692 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 25
セット名 テストケース
Sample sample_00.txt, sample_01.txt, sample_02.txt
All case_00.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, sample_00.txt, sample_01.txt, sample_02.txt
ケース名 結果 実行時間 メモリ
case_00.txt AC 659 ms 139672 KiB
case_01.txt AC 626 ms 139680 KiB
case_02.txt AC 592 ms 139720 KiB
case_03.txt AC 593 ms 139704 KiB
case_04.txt AC 604 ms 139720 KiB
case_05.txt AC 594 ms 139456 KiB
case_06.txt AC 609 ms 139964 KiB
case_07.txt AC 587 ms 139844 KiB
case_08.txt AC 602 ms 139848 KiB
case_09.txt AC 598 ms 139928 KiB
case_10.txt AC 602 ms 139820 KiB
case_11.txt AC 606 ms 139884 KiB
case_12.txt AC 585 ms 139872 KiB
case_13.txt AC 593 ms 139980 KiB
case_14.txt AC 599 ms 140020 KiB
case_15.txt AC 604 ms 139872 KiB
case_16.txt AC 601 ms 139800 KiB
case_17.txt AC 598 ms 139824 KiB
case_18.txt AC 615 ms 139692 KiB
case_19.txt AC 586 ms 139744 KiB
case_20.txt AC 1002 ms 361692 KiB
case_21.txt AC 604 ms 144640 KiB
sample_00.txt AC 71 ms 93628 KiB
sample_01.txt AC 70 ms 93840 KiB
sample_02.txt AC 69 ms 93752 KiB