結果
| 問題 |
No.1154 シュークリームゲーム（Hard）
|
| コンテスト | |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2020-07-13 08:00:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 108 ms / 2,000 ms |
| コード長 | 6,164 bytes |
| コンパイル時間 | 1,203 ms |
| コンパイル使用メモリ | 82,160 KB |
| 実行使用メモリ | 76,900 KB |
| 最終ジャッジ日時 | 2024-11-07 01:15:37 |
| 合計ジャッジ時間 | 5,619 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
from collections import deque
class BalancingTree:
def __init__(self, n):
self.N = n
self.offset = 1 << n
self.root = self.node(1 << n+1, 1 << n+1)
self.count = 0
def debug(self):
def debug_info(nd_):
# return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)
return nd_.value - self.offset
def debug_node(nd):
re = []
if nd.left:
re += debug_node(nd.left)
if nd.value: re.append(debug_info(nd))
if nd.right:
re += debug_node(nd.right)
return re
# 出力個数は調整してください
print("Debug - count =", self.count, "root =", self.root.value - self.offset, debug_node(self.root)[:50])
def append(self, v):
v += self.offset
self.count += 1
nd = self.root
while True:
if v == nd.value:
self.delete(v - self.offset)
self.count -= 1
return 0
else:
mi, ma = min(v, nd.value), max(v, nd.value)
if mi < nd.pivot:
nd.value = ma
if nd.left:
nd = nd.left
v = mi
else:
p = nd.pivot
nd.left = self.node(mi, p - (p&-p)//2)
break
else:
nd.value = mi
if nd.right:
nd = nd.right
v = ma
else:
p = nd.pivot
nd.right = self.node(ma, p + (p&-p)//2)
break
def leftmost(self, nd):
if nd.left: return self.leftmost(nd.left)
return nd
def rightmost(self, nd):
if nd.right: return self.rightmost(nd.right)
return nd
def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
v += self.offset
nd = self.root
prev = 0
if nd.value < v: prev = nd.value
while True:
if v <= nd.value:
if nd.left:
nd = nd.left
else:
return prev - self.offset
else:
prev = nd.value
if nd.right:
nd = nd.right
else:
return prev - self.offset
def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
v += self.offset
nd = self.root
prev = 0
if nd.value > v: prev = nd.value
while True:
if v < nd.value:
prev = nd.value
if nd.left:
nd = nd.left
else:
return prev - self.offset
else:
if nd.right:
nd = nd.right
else:
return prev - self.offset
@property
def max(self):
return self.find_l((1 << self.N + 1) - self.offset)
@property
def min(self):
return self.find_r(-self.offset)
def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
v += self.offset
if not nd: nd = self.root
if not prev: prev = nd
while v != nd.value:
prev = nd
if v <= nd.value:
if nd.left:
nd = nd.left
else:
return
else:
if nd.right:
nd = nd.right
else:
return
if (not nd.left) and (not nd.right):
if nd.value < prev.value:
self.count -= 1
prev.left = None
else:
self.count -= 1
prev.right = None
elif not nd.left:
if nd.value < prev.value:
self.count -= 1
prev.left = nd.right
else:
self.count -= 1
prev.right = nd.right
elif not nd.right:
if nd.value < prev.value:
self.count -= 1
prev.left = nd.left
else:
self.count -= 1
prev.right = nd.left
else:
nd.value = self.leftmost(nd.right).value
self.delete(nd.value - self.offset, nd.right, nd)
def __contains__(self, v):
return self.find_r(v - 1) == v
class node:
def __init__(self, v, p):
self.value = v
self.pivot = p
self.left = None
self.right = None
N = int(input())
A = [int(a) for a in input().split()]
E = [[] for _ in range(N)]
for _ in range(N - 1):
a, b = map(int, input().split())
E[a-1].append(b-1)
E[b-1].append(a-1)
X = [[] for i in range(N)]
P = [-1] * N
Q = deque([0])
R = []
while Q:
i = deque.popleft(Q)
R.append(i)
for a in E[i]:
if a != P[i]:
P[a] = i
E[a].remove(i)
deque.append(Q, a)
def merge(i):
mac = 0
maj = -1
for j in E[i]:
if D[j].count > mac:
mac = D[j].count
maj = j
if not mac:
return
D[i] = D[maj]
for j in E[i]:
if j == maj:
continue
while D[j].count:
mi = D[j].min
D[i].append(mi)
D[j].delete(mi)
D = [BalancingTree(50) for _ in range(N)]
ans = 0
for i in R[::-1]:
merge(i)
a = A[i]
f = 1
while D[i].count:
ma = D[i].max
if ma < a and f > 0:
break
f *= -1
a += ma * f
D[i].delete(ma)
if f == -1:
ans += a if N % 2 == 0 else -a
else:
D[i].append(a)
f = 1
while D[0].count:
ma = D[0].max
D[0].delete(ma)
ans += ma * f
f *= -1
print(ans)