結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2023-05-15 21:58:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 933 ms / 2,000 ms |
コード長 | 1,002 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 370,292 KB |
最終ジャッジ日時 | 2024-12-14 03:29:37 |
合計ジャッジ時間 | 6,843 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
class Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def _add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -idef _sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sn=int(input())rin=[[] for i in range(n)]a=list(map(int,input().split()))for i in range(1,n):rin[a[i-1]].append(i)rin[i].append(a[i-1])bit=Bit(n+2)import syssys.setrecursionlimit(10**6)kukan = [[0,0] for i in range(n)]ind=1def cal(x,pre):global indkukan[x][0] = indif len(rin[x]) == 1 and x!= pre:kukan[x][1] = indind += 1returnind += 1for i in rin[x]:if i != pre:cal(i,x)kukan[x][1] = ind-1cal(0,0)ans = 0for x in range(n-1,-1,-1):l,r=kukan[x][0],kukan[x][1]ans += bit._sum(r) - bit._sum(l-1)bit._add(l,1)print(ans)