Submission #23994024

Source Code Expand

import sys

sys.setrecursionlimit(2 ** 20)

input = sys.stdin.readline


def dfs(p, par, edge):
    res = 0
    cnt = 1
    for e in edge[p]:
        if e == par:
            continue
        r, c = dfs(e, p, edge)
        res += r
        cnt += c
    res += cnt * (len(edge) - cnt)
    return res, cnt


def main():
    n = int(input())
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = (int(i) - 1 for i in input().split())
        edge[u].append(v)
        edge[v].append(u)
    print(dfs(0, -1, edge)[0])


if __name__ == "__main__":
    main()

Submission Info

Submission Time
Task 039 - Tree Distance（★5）
User riantkb
Language Python (3.8.2)
Score 5
Code Size 576 Byte
Status AC
Exec Time 220 ms
Memory 26380 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 5 / 5
Status
AC × 3
AC × 34
Set Name Test Cases
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, 10_random_small_00.txt, 10_random_small_01.txt, 10_random_small_02.txt, 10_random_small_03.txt, 10_random_small_04.txt, 10_random_small_05.txt, 10_random_small_06.txt, 10_random_small_07.txt, 10_random_small_08.txt, 10_random_small_09.txt, 11_random_large_00.txt, 11_random_large_01.txt, 11_random_large_02.txt, 11_random_large_03.txt, 11_random_large_04.txt, 11_random_large_05.txt, 11_random_large_06.txt, 11_random_large_07.txt, 11_random_large_08.txt, 11_random_large_09.txt, 20_random_max_00.txt, 20_random_max_01.txt, 20_random_max_02.txt, 20_random_max_03.txt, 20_random_max_04.txt, 20_random_max_05.txt, 20_random_max_06.txt, 30_uni_00.txt, 30_uni_01.txt, 40_path_00.txt, 40_path_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 17 ms 9068 KiB
00_sample_01.txt AC 20 ms 8924 KiB
00_sample_02.txt AC 17 ms 9100 KiB
10_random_small_00.txt AC 19 ms 9028 KiB
10_random_small_01.txt AC 18 ms 9036 KiB
10_random_small_02.txt AC 19 ms 9036 KiB
10_random_small_03.txt AC 23 ms 8916 KiB
10_random_small_04.txt AC 21 ms 9084 KiB
10_random_small_05.txt AC 19 ms 9156 KiB
10_random_small_06.txt AC 18 ms 9024 KiB
10_random_small_07.txt AC 18 ms 9032 KiB
10_random_small_08.txt AC 17 ms 8884 KiB
10_random_small_09.txt AC 23 ms 9068 KiB
11_random_large_00.txt AC 20 ms 8988 KiB
11_random_large_01.txt AC 26 ms 9688 KiB
11_random_large_02.txt AC 33 ms 9764 KiB
11_random_large_03.txt AC 28 ms 10184 KiB
11_random_large_04.txt AC 28 ms 9972 KiB
11_random_large_05.txt AC 28 ms 9520 KiB
11_random_large_06.txt AC 32 ms 9764 KiB
11_random_large_07.txt AC 27 ms 10096 KiB
11_random_large_08.txt AC 39 ms 9920 KiB
11_random_large_09.txt AC 21 ms 9260 KiB
20_random_max_00.txt AC 220 ms 26020 KiB
20_random_max_01.txt AC 206 ms 25808 KiB
20_random_max_02.txt AC 200 ms 25620 KiB
20_random_max_03.txt AC 201 ms 25756 KiB
20_random_max_04.txt AC 198 ms 25912 KiB
20_random_max_05.txt AC 199 ms 26056 KiB
20_random_max_06.txt AC 206 ms 25708 KiB
30_uni_00.txt AC 187 ms 26380 KiB
30_uni_01.txt AC 177 ms 26212 KiB
40_path_00.txt AC 22 ms 9788 KiB
40_path_01.txt AC 40 ms 17564 KiB