結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2019-01-06 14:30:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,319 ms / 2,000 ms |
コード長 | 1,308 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 373,788 KB |
最終ジャッジ日時 | 2024-11-23 23:46:38 |
合計ジャッジ時間 | 8,790 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
class BinaryIndexedTree(object):__slots__ = ["tree"]def __init__(self, size: int):self.tree = [0]*(size+1)def add(self, index: int, value: int):tree = self.treewhile index < len(tree):tree[index] += valueindex += index & -indexdef sum(self, index: int):tree, result = self.tree, 0while index:result += tree[index]index -= index & -indexreturn resultdef euler_tour(tree):import syssys.setrecursionlimit(10**7)edges = [[] for _ in [0]*(len(tree)+1)]for origin, destination in enumerate(tree, start=1):edges[destination].append(origin)subtree_range = [[0, 0] for _ in [0]*(len(tree)+1)]def rec(v, index):subtree_range[v][0] = indexfor destination in edges[v]:index = rec(destination, index+1)subtree_range[v][1] = indexreturn index + 1rec(0, 1)return subtree_rangeif __name__ == "__main__":N = int(input())tree = list(map(int, input().split()))subtree_range = euler_tour(tree)bit = BinaryIndexedTree(2*N-1)ans = 0for start, end in subtree_range[::-1]:ans += bit.sum(end) - bit.sum(start-1)bit.add(start, 1)print(ans)