結果

問題 No.778 クリスマスツリー
ユーザー tamato
提出日時 2020-04-28 01:31:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 776 ms / 2,000 ms
コード長 2,156 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 164,300 KB
最終ジャッジ日時 2024-11-22 19:17:21
合計ジャッジ時間 7,397 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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

mod = 1000000007
eps = 10**-9
def main():
import sys
input = sys.stdin.readline
class Bit:
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
def lower_bound(self, w):
if w <= 0:
return 0
x = 0
k = 1 << (self.size.bit_length() - 1)
while k:
if x + k <= self.size and self.tree[x + k] < w:
w -= self.tree[x + k]
x += k
k >>= 1
return x + 1
# adj[0] must be empty list
def EulerTour(adj, root):
st = [root]
ret = []
seen = [0] * len(adj)
par = [0] * len(adj)
depth = [0] * len(adj)
while st:
v = st.pop()
if seen[v]:
ret.append(v)
continue
ret.append(v)
seen[v] = 1
if par[v] != 0:
st.append(par[v])
for u in adj[v]:
if seen[u] == 0:
st.append(u)
par[u] = v
depth[u] = depth[v] + 1
return ret, depth
N = int(input())
A = list(map(int, input().split()))
adj = [[] for _ in range(N+1)]
for i in range(N-1):
v = i+2
p = A[i] + 1
adj[v].append(p)
adj[p].append(v)
et, depth = EulerTour(adj,1)
bit = Bit(len(et))
cnt = [0] * (N+1)
v_idx = [[] for _ in range(N+1)]
for i, v in enumerate(et):
cnt[v] += 1
v_idx[v].append(i+1)
for i, v in enumerate(et):
bit.add(i+1, 1 / cnt[v])
ans = 0
for v in range(1, N+1):
ans += bit.sum(v_idx[v][-1]) - bit.sum(v_idx[v][0]-1) - 1
for i in v_idx[v]:
bit.add(i, -1 / cnt[v])
print(round(ans))
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0