結果
問題 | No.1103 Directed Length Sum |
ユーザー | tonnnura172 |
提出日時 | 2020-07-11 05:20:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,652 ms / 3,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 2,313 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 263,648 KB |
最終ジャッジ日時 | 2024-04-20 11:58:14 |
合計ジャッジ時間 | 15,056 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
65,536 KB |
testcase_01 | AC | 59 ms
65,536 KB |
testcase_02 | AC | 659 ms
263,648 KB |
testcase_03 | AC | 592 ms
262,796 KB |
testcase_04 | AC | 936 ms
183,168 KB |
testcase_05 | AC | 1,652 ms
235,456 KB |
testcase_06 | AC | 508 ms
145,664 KB |
testcase_07 | AC | 150 ms
93,312 KB |
testcase_08 | AC | 196 ms
100,780 KB |
testcase_09 | AC | 117 ms
86,320 KB |
testcase_10 | AC | 254 ms
110,336 KB |
testcase_11 | AC | 881 ms
193,920 KB |
testcase_12 | AC | 478 ms
146,048 KB |
testcase_13 | AC | 246 ms
112,896 KB |
testcase_14 | AC | 110 ms
83,968 KB |
testcase_15 | AC | 490 ms
131,072 KB |
testcase_16 | AC | 1,019 ms
207,488 KB |
testcase_17 | AC | 1,145 ms
195,256 KB |
testcase_18 | AC | 246 ms
110,336 KB |
testcase_19 | AC | 969 ms
195,808 KB |
testcase_20 | AC | 138 ms
87,936 KB |
testcase_21 | AC | 187 ms
99,584 KB |
testcase_22 | AC | 709 ms
161,152 KB |
testcase_23 | AC | 433 ms
135,552 KB |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2 from itertools import accumulate, permutations, combinations, product from operator import itemgetter, mul, add from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce, lru_cache def input(): return sys.stdin.buffer.readline().rstrip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 N = INT() tree = [[] for _ in range(N)] din = [0]*N for _ in range(N-1): A, B = MAP() tree[A-1].append(B-1) din[B-1] += 1 root = din.index(0) size_d = [0]*N size_u = [0]*N parent = [0]*N order = [] stack = [root] while stack: x = stack.pop() size_u[x] += 1 order.append(x) for y in tree[x]: size_u[y] += size_u[x] parent[y] = x stack.append(y) ans = 0 for v in order[::-1]: size_d[v] += 1 if v == root: break p = parent[v] s = size_d[v] ans += s * size_u[p] ans %= mod size_d[p] += s print(ans)