結果

問題 No.778 クリスマスツリー
ユーザー H3PO4
提出日時 2021-02-02 10:06:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,650 ms / 2,000 ms
コード長 689 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 81,184 KB
最終ジャッジ日時 2024-06-29 23:37:41
合計ジャッジ時間 13,226 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
sys.setrecursionlimit(10 ** 9)
class Bit:
"""1-indexed"""
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
N = int(input())
A = map(int, input().split())
T = [[] for _ in range(N)]
for i, a in enumerate(A, 1):
T[a].append(i)
bit = Bit(N)
def dfs(v):
res = bit.sum(v)
bit.add(v + 1, 1)
for x in T[v]:
res += dfs(x)
bit.add(v + 1, -1)
return res
print(dfs(0))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0