結果
問題 | No.1103 Directed Length Sum |
ユーザー | tonnnura172 |
提出日時 | 2020-07-11 05:19:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,499 ms / 3,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 263,564 KB |
最終ジャッジ日時 | 2024-04-20 11:55:40 |
合計ジャッジ時間 | 13,981 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 57 ms
66,176 KB |
testcase_01 | AC | 56 ms
66,000 KB |
testcase_02 | AC | 540 ms
263,564 KB |
testcase_03 | AC | 432 ms
262,924 KB |
testcase_04 | AC | 845 ms
182,956 KB |
testcase_05 | AC | 1,499 ms
235,916 KB |
testcase_06 | AC | 527 ms
145,716 KB |
testcase_07 | AC | 145 ms
93,572 KB |
testcase_08 | AC | 198 ms
100,600 KB |
testcase_09 | AC | 116 ms
86,584 KB |
testcase_10 | AC | 271 ms
110,636 KB |
testcase_11 | AC | 912 ms
193,632 KB |
testcase_12 | AC | 506 ms
145,988 KB |
testcase_13 | AC | 259 ms
112,652 KB |
testcase_14 | AC | 110 ms
84,112 KB |
testcase_15 | AC | 417 ms
131,504 KB |
testcase_16 | AC | 1,004 ms
208,296 KB |
testcase_17 | AC | 1,088 ms
195,432 KB |
testcase_18 | AC | 261 ms
110,576 KB |
testcase_19 | AC | 962 ms
195,764 KB |
testcase_20 | AC | 130 ms
87,972 KB |
testcase_21 | AC | 183 ms
99,228 KB |
testcase_22 | AC | 768 ms
161,332 KB |
testcase_23 | AC | 422 ms
135,828 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()[:-1] 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)