結果
問題 |
No.778 クリスマスツリー
|
ユーザー |
![]() |
提出日時 | 2023-05-15 21:46:44 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 981 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,500 KB |
実行使用メモリ | 132,928 KB |
最終ジャッジ日時 | 2024-12-14 03:24:37 |
合計ジャッジ時間 | 5,159 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | WA * 9 RE * 3 |
ソースコード
class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def _add(self, i, x): while i <= self.size: self.tree[i] += x i += i & -i def _sum(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & -i return s n=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) kukan = [[0,0] for i in range(n)] ind=1 def cal(x,pre): global ind kukan[x][0] = ind if len(rin[x]) == 1 and x!= pre: ind += 1 kukan[x][1] = ind return ind += 1 for i in rin[x]: if i != pre: cal(i,x) kukan[x][1] = ind cal(0,0) ans = 0 for 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)