結果
問題 | No.1103 Directed Length Sum |
ユーザー | nephrologist |
提出日時 | 2020-07-03 22:49:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,098 ms / 3,000 ms |
コード長 | 2,694 bytes |
コンパイル時間 | 472 ms |
コンパイル使用メモリ | 81,596 KB |
実行使用メモリ | 346,976 KB |
最終ジャッジ日時 | 2023-10-17 05:51:14 |
合計ジャッジ時間 | 20,392 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,456 KB |
testcase_01 | AC | 39 ms
53,456 KB |
testcase_02 | AC | 1,046 ms
346,976 KB |
testcase_03 | AC | 962 ms
344,924 KB |
testcase_04 | AC | 1,207 ms
208,452 KB |
testcase_05 | AC | 2,098 ms
264,444 KB |
testcase_06 | AC | 805 ms
164,880 KB |
testcase_07 | AC | 258 ms
96,280 KB |
testcase_08 | AC | 364 ms
121,976 KB |
testcase_09 | AC | 219 ms
91,468 KB |
testcase_10 | AC | 453 ms
134,440 KB |
testcase_11 | AC | 1,334 ms
223,624 KB |
testcase_12 | AC | 830 ms
169,228 KB |
testcase_13 | AC | 476 ms
139,040 KB |
testcase_14 | AC | 185 ms
88,180 KB |
testcase_15 | AC | 671 ms
149,588 KB |
testcase_16 | AC | 1,514 ms
238,456 KB |
testcase_17 | AC | 1,566 ms
230,628 KB |
testcase_18 | AC | 460 ms
134,580 KB |
testcase_19 | AC | 1,371 ms
233,612 KB |
testcase_20 | AC | 228 ms
97,564 KB |
testcase_21 | AC | 325 ms
113,832 KB |
testcase_22 | AC | 1,157 ms
196,188 KB |
testcase_23 | AC | 725 ms
163,320 KB |
ソースコード
# 1-idx # LCAっぽい気がしている。 # 長さから含まれるpathの総和は求められる # 包除原理っぽくやる。 import sys input = sys.stdin.buffer.readline mod = 10 ** 9 + 7 n = int(input()) graph = [[] for _ in range(n + 1)] in_num = [0] * (n + 1) par = [-1] * (n + 1) for _ in range(n - 1): a, b = map(int, input().split()) par[b] = a graph[a].append(b) root = -1 # 根がどれか確認 for i in range(1, n + 1): if par[i] == -1: root = i assert root > 0 # 考慮すべき葉のリストを作る mattan = [] # 長さi経路に含まれるpathの和 def path_calc(length): return (length * (length + 1) * (length + 2) // 6) % mod # LCAの準備のeuler&first&depth heavyはいらんな。 def dfs(start): idx = 0 euler = [] depth = [-1] * (n + 1) depth[start] = 0 stack = [] first = [-1] * (n + 1) stack.append(~start) stack.append(start) while stack: v = stack.pop() if v > 0: d = depth[v] euler.append(v) first[v] = idx idx += 1 # 子供がないところは末端。 if not graph[v]: mattan.append(v) for u in graph[v]: depth[u] = d + 1 stack.append(~u) stack.append(u) else: a = ~v euler.append(par[a]) idx += 1 return depth, euler, first depth, euler, first = dfs(root) # segment tree nagasa = len(euler) num = 2 ** (nagasa.bit_length()) infi = 10 ** 10 SEG = [infi] * (2 * num) def func(a, b): return min(a, b) def update(idx, val): idx += num SEG[idx] = val while idx > 0: idx //= 2 SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1]) def query(a, b): # 閉区間。 res = infi a += num b += num while b - a > 0: if (a & 1) == 1: res = func(res, SEG[a]) a += 1 if (b & 1) == 0: res = func(res, SEG[b]) b -= 1 a //= 2 b //= 2 if a == b: res = func(SEG[a], res) return res for idx, val in enumerate(euler): update(idx, depth[val]) nagasa = len(mattan) if nagasa == 1: ans = path_calc(depth[mattan[-1]]) % mod else: ans = path_calc(depth[mattan[0]]) % mod for i in range(1, nagasa): # print(ans) now = mattan[i] NOW = first[now] pre = mattan[i - 1] PRE = first[pre] ans += path_calc(depth[now]) ans %= mod if NOW < PRE: NOW, PRE = PRE, NOW sosen = query(PRE, NOW) ans -= path_calc(sosen) ans %= mod print(ans)