結果

問題 No.778 クリスマスツリー
コンテスト
ユーザー るこーそー
提出日時 2025-03-25 14:37:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 862 ms / 2,000 ms
コード長 1,070 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 340,652 KB
最終ジャッジ日時 2025-03-25 14:37:34
合計ジャッジ時間 6,759 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    def __init__(self,n):
        self.n=n
        self.d=[0]*(n+1)
    def add(self,i,x):
        i+=1
        while i<=self.n:
            self.d[i]+=x
            i+=i&-i
    def _sum(self,i):
        res=0
        i+=1
        while i>0:
            res+=self.d[i]
            i-=i&-i
        return res
    def sum(self,l,r):
        return self._sum(r-1)-self._sum(l-1)
    def max_right(self,l,f):
        if l==self.n:
            return self.n
        s=self._sum(l)  
        pos=l
        bit_mask=1<<(self.n.bit_length()-1)
        while bit_mask:
            nxt=pos+bit_mask
            if nxt<=self.n and f(s+self.d[nxt]):
                s+=self.d[nxt]
                pos=nxt
            bit_mask>>=1
        return pos
   
import sys
sys.setrecursionlimit(2*10**5)
 
n=int(input())
A=list(map(int,input().split()))

g=[[] for _ in range(n)]
for i in range(n-1):
    g[A[i]].append(i+1)

bit=BIT(n)
ans=0
def dfs(v):
    global ans
    ans+=bit.sum(0,v)
    bit.add(v,1)
    for nv in g[v]:
        dfs(nv)
    bit.add(v,-1)
dfs(0)
print(ans)
0