結果
| 問題 | No.3755 Root for Your Route |
| コンテスト | |
| ユーザー |
 marc2825
|
| 提出日時 | 2026-08-19 23:44:48 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 8,273 bytes |
| 記録 | |
| コンパイル時間 | 68 ms |
| コンパイル使用メモリ | 84,216 KB |
| 実行使用メモリ | 275,192 KB |
| 最終ジャッジ日時 | 2026-10-02 21:03:18 |
| 合計ジャッジ時間 | 47,031 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 36 WA * 3 |
ソースコード
import sys
# 再帰上限の引き上げ
sys.setrecursionlimit(200000)
def solve():
# 入力を一括で読み込み
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
A = [0] * (N + 1)
for i in range(1, N + 1):
A[i] = int(input_data[i])
adj = [[] for _ in range(N + 1)]
idx = N + 1
for _ in range(N - 1):
u = int(input_data[idx])
v = int(input_data[idx+1])
idx += 2
adj[u].append(v)
adj[v].append(u)
INF = 4 * 10**18
# -----------------------------------------------------
# Li Chao Tree (タイムスタンプ世代管理付き・非再帰)
# -----------------------------------------------------
size = 1
while size <= N + 5:
size *= 2
lct_a = [0] * (2 * size)
lct_b = [-INF] * (2 * size)
lct_time = [0] * (2 * size)
state = {'time': 1}
def add_line(a, b):
curr_time = state['time']
idx = 1
L = 0
R = size - 1
while True:
# 世代が古いノードを上書き
if lct_time[idx] != curr_time:
lct_a[idx] = a
lct_b[idx] = b
lct_time[idx] = curr_time
break
mid = (L + R) >> 1
a_idx = lct_a[idx]
b_idx = lct_b[idx]
v_mid = a_idx * mid + b_idx
n_mid = a * mid + b
v_L = a_idx * L + b_idx
n_L = a * L + b
# 中央の評価値が高いなら直線を入れ替え
if n_mid > v_mid:
lct_a[idx] = a
lct_b[idx] = b
a = a_idx
b = b_idx
if L == R:
break
if (n_L > v_L) != (n_mid > v_mid):
idx = idx << 1
R = mid
else:
idx = (idx << 1) | 1
L = mid + 1
def query_line(x):
curr_time = state['time']
idx = 1
L = 0
R = size - 1
res = -INF
while True:
# 現在の世代と一致する場合のみ計算
if lct_time[idx] == curr_time:
val = lct_a[idx] * x + lct_b[idx]
if val > res:
res = val
else:
break
if L == R:
break
mid = (L + R) >> 1
if x <= mid:
idx = idx << 1
R = mid
else:
idx = (idx << 1) | 1
L = mid + 1
return res
# -----------------------------------------------------
# 重心分解 関連の変数準備
# -----------------------------------------------------
used = [False] * (N + 1)
M = [-INF] * (N + 1)
for i in range(1, N + 1):
M[i] = A[i]
val = [-INF] * (N + 1)
depth_c = [0] * (N + 1)
parent_c = [0] * (N + 1)
sum_c = [0] * (N + 1)
U_c = [0] * (N + 1)
# -----------------------------------------------------
# 分割統治 (Divide and Conquer) によるパス最大化
# -----------------------------------------------------
def DC(l, r, subtrees, sub_lines, A_c):
if l == r:
return
mid = (l + r) >> 1
# 左から右へのマッチング
state['time'] += 1
for i in range(l, mid + 1):
for d, u in sub_lines[i]:
add_line(-d, u)
for i in range(mid + 1, r + 1):
for v in subtrees[i]:
res = query_line(depth_c[v])
if res != -INF:
E = res + U_c[v] - A_c
if E > val[v]: val[v] = E
# 右から左へのマッチング
state['time'] += 1
for i in range(mid + 1, r + 1):
for d, u in sub_lines[i]:
add_line(-d, u)
for i in range(l, mid + 1):
for v in subtrees[i]:
res = query_line(depth_c[v])
if res != -INF:
E = res + U_c[v] - A_c
if E > val[v]: val[v] = E
DC(l, mid, subtrees, sub_lines, A_c)
DC(mid + 1, r, subtrees, sub_lines, A_c)
# -----------------------------------------------------
# 重心分解の本体
# -----------------------------------------------------
def decompose(start_node):
# 1. 部分木のサイズを計算して重心を特定
q = [start_node]
order = []
parent = {start_node: -1}
head = 0
while head < len(q):
u = q[head]; head += 1
order.append(u)
for v in adj[u]:
if not used[v] and v != parent[u]:
parent[v] = u
q.append(v)
sz = {u: 1 for u in order}
for u in reversed(order):
p = parent[u]
if p != -1:
sz[p] += sz[u]
total = sz[start_node]
c = start_node
while True:
nxt = -1
for v in adj[c]:
if not used[v] and v != parent[c] and sz[v] > total // 2:
nxt = v
break
if nxt != -1:
c = nxt
else:
break
used[c] = True
# 2. 重心を起点とした部分木の情報を集める
subtrees = [[c]]
A_c = A[c]
depth_c[c] = 0
U_c[c] = A[c]
parent_c[c] = c
for v in adj[c]:
if not used[v]:
sub = []
sq = [v]
head = 0
depth_c[v] = 1
parent_c[v] = c
sum_c[v] = A[c] + A[v]
U_c[v] = sum_c[v] - 1
# BFSで部分木内の距離とスコアを計算
while head < len(sq):
u = sq[head]; head += 1
sub.append(u)
for nxt_v in adj[u]:
if not used[nxt_v] and nxt_v != parent_c[u]:
parent_c[nxt_v] = u
depth_c[nxt_v] = depth_c[u] + 1
sum_c[nxt_v] = sum_c[u] + A[nxt_v]
d = depth_c[nxt_v]
U_c[nxt_v] = sum_c[nxt_v] - d * (d + 1) // 2
sq.append(nxt_v)
subtrees.append(sub)
K = len(subtrees)
sub_lines = []
# 不要な直線の追加を防ぐため、同じ深さからは最大スコアだけを抽出
for i in range(K):
max_u = {}
for u in subtrees[i]:
d = depth_c[u]
u_val = U_c[u]
if d not in max_u or u_val > max_u[d]:
max_u[d] = u_val
sub_lines.append(list(max_u.items()))
# 3. 分割統治と葉から根への伝播
if K > 1:
DC(0, K - 1, subtrees, sub_lines, A_c)
# BFSの訪問順序を逆順に辿ることで「葉から根」に伝播
for i in range(1, K):
for v in reversed(subtrees[i]):
p = parent_c[v]
if p != c and val[v] > val[p]:
val[p] = val[v]
# 全体の答え配列に反映させつつ一時配列をクリーンアップ
for i in range(K):
for v in subtrees[i]:
if val[v] > M[v]: M[v] = val[v]
val[v] = -INF
# 4. 次の重心へ再帰
for v in adj[c]:
if not used[v]:
decompose(v)
# 処理開始
decompose(1)
# 全頂点の中でスコア最小となるものを探索
ans = min(M[1:])
print(ans)
if __name__ == '__main__':
solve()