結果

問題 No.778 クリスマスツリー
ユーザー SI1000-github
提出日時 2022-03-31 14:40:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,669 ms / 2,000 ms
コード長 5,662 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 436,688 KB
最終ジャッジ日時 2024-11-16 21:57:07
合計ジャッジ時間 12,588 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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

#!/usr/bin/python
# -*- coding: utf-8 -*-
# import
from sys import stdin, setrecursionlimit
setrecursionlimit(10**8)
# def
def int_map():
return map(int,input().split())
def int_list():
return ['Null']+list(map(int,input().split()))
# N+1
def int_mtx(N):
x = [['Null']+list(map(int, stdin.readline().split())) for _ in range(N)]
x.insert(0,['Null'])
return x
# N+1
# AAAAA
# BBBBB
# CCCCC
#
# '0AAAAA'
# '0BBBBB'
# '0CCCCC'
#
def str_mtx(N):
x = ['0'+stdin.readline()[:-1] for _ in range(N)]
x.insert(0,'0')
return x
# N+1
# AAAAA XXXXX
# BBBBB YYYYY
# CCCCC ZZZZZ
#
# [[['0'],[AAAAA],[XXXXX]],
# [['0'],[BBBBB],[YYYYY]],
# [['0'],[CCCCC],[ZZZZZ]] ]
#
def str_list(N):
x = [['0']+list(map(str, stdin.readline().split())) for _ in range(N)]
x.insert(0,['0'])
return x
# H+1, W+1,
def zero_mtx(H,W):
x = [[0]*(W+1) for i in range(H+1)]
return x
#
def print_space(l):
return print(" ".join([str(x) for x in l[1:]]))
#
# N
def int_mtx_0(N):
x = [list(map(int, stdin.readline().split())) for _ in range(N)]
return x
#
# N+1
def str_mtx_0(N):
x = [list(stdin.readline()[:-1]) for _ in range(N)]
return x
#
#
def print_space_0(l):
return print(" ".join([str(x) for x in l]))
#
# H, W,
def zero_mtx_0(H,W):
x = [[0]*W for i in range(H)]
return x
def int_list_0():
return list(map(int,input().split()))
##
# from collections import deque
# 使
# import itertools
# 使
# import math
# dict
# import collections
#
# a_copy = deepcopy(a)
# from copy import deepcopy
from collections import deque, defaultdict
#
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
N = int(input())
# UV
cccc = int_list_0()
UV = []
for i in range(N-1):
UV.append([i+1,cccc[i]])
root_id = 0
G = [[] for _ in range(N)]
for ui,vi in UV:
G[ui].append(vi)
G[vi].append(ui)
# Euler Tour Technique
S = []
AS = defaultdict(list)
def dfs(v, p, d):
AS[v].append(len(S))
S.append(v)
for w in G[v]:
if w == p:
continue
dfs(w, v, d+1)
AS[v].append(len(S))
S.append(v)
dfs(root_id, -1, 0)
class SegTree:
def __init__(self, A, SegType):
if SegType == "min":
self.X_f = min
self.X_unit = float('inf')
elif SegType == "max":
self.X_f = max
self.X_unit = -float('inf')
elif SegType == "sum":
def segfunc(x, y):
return x+y
self.X_f = segfunc
self.X_unit = 0
elif SegType == "pro":
def segfunc(x, y):
return x*y
self.X_f = segfunc
self.X_unit = 1
elif SegType == "xor":
def segfunc(x, y):
return x^y
self.X_f = segfunc
self.X_unit = 0
elif SegType == "gcd":
from math import gcd
self.X_f = gcd
self.X_unit = 0
elif SegType == "lcm":
from math import gcd
def lcm(a,b):
return a//gcd(a,b)*b
self.X_f = lcm
self.X_unit = 1
self.N = len(A)
self.X = [self.X_unit] * (self.N + self.N)
self.build(A)
def leaf(self):
return self.X[self.N:]
def build(self, seq):
for i, x in enumerate(seq, self.N):
self.X[i] = x
for i in range(self.N - 1, 0, -1):
self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])
def set_val(self, i, x):
i += self.N
self.X[i] = x
while i > 1:
i >>= 1
self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])
def add_val(self, i, x):
i += self.N
self.X[i] += x
while i > 1:
i >>= 1
self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])
def fold(self, L, R):
L += self.N
R += self.N
vL = self.X_unit
vR = self.X_unit
while L < R:
if L & 1:
vL = self.X_f(vL, self.X[L])
L += 1
if R & 1:
R -= 1
vR = self.X_f(self.X[R], vR)
L >>= 1
R >>= 1
return self.X_f(vL, vR)
A = [0]*len(S)
SegType = "sum"
seg = SegTree(A, SegType)
ans = 0
for i in reversed(range(N)):
l = AS[i][0]
r = AS[i][-1]
ans += seg.fold(l,r+1)
seg.set_val(AS[i][0],1)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0