#1177704 (PyPy3) No.3755 Root for Your Route

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:42:59
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 2,014 ms / 3,000 ms
• コード長: 6,499 bytes
• コンパイル時間: 1,989 ms
• コンパイル使用メモリ: 83,808 KB
• 実行使用メモリ: 216,396 KB
• 最終ジャッジ日時: 2026-10-02 21:02:48
• 合計ジャッジ時間: 45,542 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

import sys
sys.setrecursionlimit(1_000_000)

input = sys.stdin.readline

NEG = -(10 ** 60)


# 最大値 Li Chao Tree
class LiChao:
    __slots__ = ("X", "seg")

    def __init__(self, X):
        self.X = X
        self.seg = [None] * (4 * (X + 1) + 5)

    def clear(self):
        self.seg = [None] * len(self.seg)

    # y = m*x + b を追加
    def add_line(self, m, b):
        seg = self.seg
        X = self.X

        k = 1
        l = 0
        r = X

        while True:
            cur = seg[k]

            if cur is None:
                seg[k] = (m, b)
                return

            cm, cb = cur
            mid = (l + r) >> 1

            left_better = m * l + b > cm * l + cb
            mid_better = m * mid + b > cm * mid + cb

            if mid_better:
                seg[k] = (m, b)
                m, b = cm, cb

            if l == r:
                return

            if left_better != mid_better:
                k <<= 1
                r = mid
            else:
                k = k * 2 + 1
                l = mid + 1

    def query(self, x):
        seg = self.seg
        X = self.X

        k = 1
        l = 0
        r = X

        res = NEG

        while True:
            cur = seg[k]

            if cur is not None:
                m, b = cur
                val = m * x + b
                if val > res:
                    res = val

            if l == r:
                return res

            mid = (l + r) >> 1

            if x <= mid:
                k <<= 1
                r = mid
            else:
                k = k * 2 + 1
                l = mid + 1


N = int(input())
A = list(map(int, input().split()))

G = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    G[u].append(v)
    G[v].append(u)


sub = [0] * N
par = [-1] * N
dead = [False] * N

# ans[r] =
# r を通る単純パスの最大スコア
#
# s=t=r は常に選べるので A[r] で初期化
ans = A[:]

other_best = [NEG] * N
cur = [NEG] * N


# 現在の成分の重心を求める
def get_centroid(start):
    order = []
    stack = [start]

    par[start] = -1

    while stack:
        u = stack.pop()
        order.append(u)

        pu = par[u]

        for v in G[u]:
            if dead[v] or v == pu:
                continue

            par[v] = u
            stack.append(v)

    # subtree size
    for u in order:
        sub[u] = 1

    for u in reversed(order):
        p = par[u]

        if p != -1:
            sub[p] += sub[u]

    total = len(order)
    half = total // 2

    for u in order:
        # 親側
        mx = total - sub[u]

        for v in G[u]:
            if dead[v]:
                continue

            if par[v] == u:
                if sub[v] > mx:
                    mx = sub[v]

        if mx <= half:
            return u

    assert False


# 重心 c の隣接 component を集める
#
# B_v =
#   sum(c -> v) - depth*(depth+1)/2
#
# B_child = B_parent + A[child] - depth_child
def collect_component(c, first):
    res = []

    # first の depth = 1
    first_B = A[c] + A[first] - 1

    stack = [
        (first, c, 1, first_B)
    ]

    max_depth = 0

    while stack:
        u, p, d, B = stack.pop()

        res.append((u, p, d, B))

        if d > max_depth:
            max_depth = d

        nd = d + 1

        for v in G[u]:
            if dead[v] or v == p:
                continue

            # B_v = B_u + A[v] - nd
            stack.append(
                (v, u, nd, B + A[v] - nd)
            )

    return res, max_depth


def process_centroid(c):
    Ac = A[c]

    comps = []
    max_depth = 0

    # c を削除したときの各連結成分
    for v in G[c]:
        if dead[v]:
            continue

        comp, md = collect_component(c, v)

        comps.append(comp)

        if md > max_depth:
            max_depth = md

    if not comps:
        return

    # -------------------------------------------------
    # 重心 c を通るパス
    #
    # x, y が異なる component にいるとする。
    #
    # d_x = dist(c,x)
    # d_y = dist(c,y)
    #
    # B_x = sum(c->x) - d_x(d_x+1)/2
    #
    # score(x,y)
    # = B_x + B_y - A[c] - d_x*d_y
    #
    # x 固定なら
    #
    # max_y (B_y - d_x*d_y)
    #
    # y を
    #
    # f_y(X) = -d_y X + B_y
    #
    # という直線にする。
    # -------------------------------------------------

    hull = LiChao(max_depth)

    # y = c も候補
    #
    # d_c = 0
    # B_c = A[c]
    hull.add_line(0, Ac)

    # 左 -> 右
    #
    # query 後に current component を追加することで
    # 同一 component 同士を選ばない
    best_c = ans[c]

    for comp in comps:

        for u, p, d, B in comp:
            q = hull.query(d)

            other_best[u] = q

            score = B - Ac + q

            if score > best_c:
                best_c = score

        for u, p, d, B in comp:
            hull.add_line(-d, B)

    ans[c] = best_c

    # 右 -> 左
    #
    # 左側 component だけでなく
    # 右側 component も候補にする
    hull.clear()
    hull.add_line(0, Ac)

    for comp in reversed(comps):

        for u, p, d, B in comp:
            q = hull.query(d)

            if q > other_best[u]:
                other_best[u] = q

        for u, p, d, B in comp:
            hull.add_line(-d, B)

    # -------------------------------------------------
    # 各 r に答えを配る
    #
    # r が c 側 component にあるとする。
    #
    # c を通るパスが r も通るためには
    # component 側の端点 x が
    # 「c を根とした r の subtree」
    # に存在すればよい。
    #
    # よって x ごとの値を subtree max で伝播する。
    # -------------------------------------------------

    for comp in comps:

        # x 自身を endpoint とした場合
        for u, p, d, B in comp:
            cur[u] = B - Ac + other_best[u]

        # collect_component は親→子の順
        # reverse すれば子→親
        for u, p, d, B in reversed(comp):
            val = cur[u]

            if val > ans[u]:
                ans[u] = val

            if p != c and val > cur[p]:
                cur[p] = val


def decompose(start):
    c = get_centroid(start)

    process_centroid(c)

    dead[c] = True

    for v in G[c]:
        if not dead[v]:
            decompose(v)


decompose(0)

# Bob は Alice の最大得点を最小にする
print(min(ans))