提出 #48583088

ソースコード 拡げる

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)


def dfs(graph, node, parent, degrees):
    degrees[node] = 1  # 初期化

    for neighbor in graph[node]:
        if neighbor != parent:
            degrees[node] += dfs(graph, neighbor, node, degrees)  # 再帰的に次数を計算

    return degrees[node]

def calculate_degrees(graph, root):
    degrees = [0] * (len(graph) + 1)
    dfs(graph, root, 0, degrees)
    return degrees[1:]  # 1-indexedのため、0番目は無視して返す


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


graph = defaultdict(list)
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

root = 1  
degrees = calculate_degrees(graph, root)
dep = []
for g in graph[1]:
    dep.append(degrees[g-1])
print(n-max(dep))

提出情報

提出日時
問題 D - Erase Leaves
ユーザ rsypoz
言語 Python (CPython 3.11.4)
得点 400
コード長 920 Byte
結果 AC
実行時間 1200 ms
メモリ 165376 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 49
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 11 ms 9400 KiB
00_sample_01.txt AC 11 ms 9380 KiB
00_sample_02.txt AC 11 ms 9336 KiB
01_random_03.txt AC 753 ms 92360 KiB
01_random_04.txt AC 1158 ms 165308 KiB
01_random_05.txt AC 1011 ms 97144 KiB
01_random_06.txt AC 746 ms 92412 KiB
01_random_07.txt AC 1153 ms 165376 KiB
01_random_08.txt AC 963 ms 97080 KiB
01_random_09.txt AC 764 ms 99444 KiB
01_random_10.txt AC 1152 ms 140104 KiB
01_random_11.txt AC 953 ms 97124 KiB
01_random_12.txt AC 993 ms 97736 KiB
01_random_13.txt AC 763 ms 99568 KiB
01_random_14.txt AC 1200 ms 155188 KiB
01_random_15.txt AC 998 ms 97096 KiB
01_random_16.txt AC 1012 ms 97732 KiB
01_random_17.txt AC 763 ms 99404 KiB
01_random_18.txt AC 1142 ms 144004 KiB
01_random_19.txt AC 972 ms 97136 KiB
01_random_20.txt AC 982 ms 97712 KiB
01_random_21.txt AC 765 ms 99292 KiB
01_random_22.txt AC 1188 ms 164312 KiB
01_random_23.txt AC 965 ms 97124 KiB
01_random_24.txt AC 1018 ms 97696 KiB
01_random_25.txt AC 124 ms 25572 KiB
01_random_26.txt AC 141 ms 37204 KiB
01_random_27.txt AC 472 ms 58100 KiB
01_random_28.txt AC 122 ms 24488 KiB
01_random_29.txt AC 603 ms 80320 KiB
01_random_30.txt AC 904 ms 96408 KiB
01_random_31.txt AC 703 ms 79880 KiB
01_random_32.txt AC 512 ms 72064 KiB
01_random_33.txt AC 333 ms 69952 KiB
01_random_34.txt AC 880 ms 94984 KiB
01_random_35.txt AC 68 ms 17144 KiB
01_random_36.txt AC 133 ms 26124 KiB
01_random_37.txt AC 365 ms 49532 KiB
01_random_38.txt AC 29 ms 11728 KiB
01_random_39.txt AC 775 ms 101664 KiB
01_random_40.txt AC 1128 ms 134636 KiB
01_random_41.txt AC 972 ms 97164 KiB
01_random_42.txt AC 998 ms 97520 KiB
01_random_43.txt AC 773 ms 100372 KiB
01_random_44.txt AC 1137 ms 134748 KiB
01_random_45.txt AC 955 ms 97096 KiB
01_random_46.txt AC 985 ms 97692 KiB
01_random_47.txt AC 11 ms 9420 KiB
01_random_48.txt AC 11 ms 9244 KiB