結果
問題 | No.1103 Directed Length Sum |
ユーザー | tonnnura172 |
提出日時 | 2020-07-11 05:19:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,350 ms / 3,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 1,237 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 264,028 KB |
最終ジャッジ日時 | 2023-08-02 12:01:57 |
合計ジャッジ時間 | 16,287 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
79,840 KB |
testcase_01 | AC | 151 ms
80,088 KB |
testcase_02 | AC | 614 ms
262,268 KB |
testcase_03 | AC | 510 ms
264,028 KB |
testcase_04 | AC | 767 ms
187,076 KB |
testcase_05 | AC | 1,350 ms
239,320 KB |
testcase_06 | AC | 502 ms
149,520 KB |
testcase_07 | AC | 225 ms
97,444 KB |
testcase_08 | AC | 259 ms
104,632 KB |
testcase_09 | AC | 196 ms
89,704 KB |
testcase_10 | AC | 387 ms
114,320 KB |
testcase_11 | AC | 822 ms
198,040 KB |
testcase_12 | AC | 503 ms
149,840 KB |
testcase_13 | AC | 308 ms
116,476 KB |
testcase_14 | AC | 204 ms
88,076 KB |
testcase_15 | AC | 431 ms
135,444 KB |
testcase_16 | AC | 929 ms
212,076 KB |
testcase_17 | AC | 994 ms
198,544 KB |
testcase_18 | AC | 338 ms
114,332 KB |
testcase_19 | AC | 977 ms
199,460 KB |
testcase_20 | AC | 219 ms
91,676 KB |
testcase_21 | AC | 272 ms
102,808 KB |
testcase_22 | AC | 761 ms
164,912 KB |
testcase_23 | AC | 460 ms
139,660 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)