結果
問題 | No.1103 Directed Length Sum |
ユーザー | tonnnura172 |
提出日時 | 2020-07-11 05:07:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,752 ms / 3,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 270,900 KB |
最終ジャッジ日時 | 2024-04-20 11:07:36 |
合計ジャッジ時間 | 18,370 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
65,664 KB |
testcase_01 | AC | 71 ms
65,664 KB |
testcase_02 | AC | 707 ms
263,424 KB |
testcase_03 | AC | 617 ms
270,900 KB |
testcase_04 | AC | 1,036 ms
165,888 KB |
testcase_05 | AC | 1,752 ms
243,928 KB |
testcase_06 | AC | 620 ms
137,144 KB |
testcase_07 | AC | 203 ms
93,952 KB |
testcase_08 | AC | 274 ms
102,912 KB |
testcase_09 | AC | 160 ms
87,168 KB |
testcase_10 | AC | 345 ms
111,744 KB |
testcase_11 | AC | 1,080 ms
184,576 KB |
testcase_12 | AC | 622 ms
137,600 KB |
testcase_13 | AC | 344 ms
113,280 KB |
testcase_14 | AC | 146 ms
85,120 KB |
testcase_15 | AC | 507 ms
128,000 KB |
testcase_16 | AC | 1,221 ms
191,260 KB |
testcase_17 | AC | 1,303 ms
194,560 KB |
testcase_18 | AC | 340 ms
111,104 KB |
testcase_19 | AC | 1,137 ms
195,840 KB |
testcase_20 | AC | 171 ms
89,728 KB |
testcase_21 | AC | 260 ms
97,792 KB |
testcase_22 | AC | 997 ms
173,056 KB |
testcase_23 | AC | 560 ms
135,808 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.readline().strip() 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]: # 根に遠いほうから(down方向のボトムアップ) 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)