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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:45:58
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 1,378 ms / 3,000 ms
• コード長: 4,945 bytes
• コンパイル時間: 66 ms
• コンパイル使用メモリ: 83,308 KB
• 実行使用メモリ: 210,768 KB
• 最終ジャッジ日時: 2026-10-02 21:03:46
• 合計ジャッジ時間: 28,942 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

from collections import deque

INF = 10**30


class LiChao:
    def __init__(self, n):
        self.n = n
        self.seg = [None] * (4 * n)

    def add(self, a, b):
        k, l, r = 1, 0, self.n - 1

        while True:
            if self.seg[k] is None:
                self.seg[k] = (a, b)
                return

            c, d = self.seg[k]
            m = (l + r) // 2

            if a * m + b > c * m + d:
                self.seg[k], (a, b) = (a, b), (c, d)

            if l == r:
                return

            c, d = self.seg[k]

            if a * l + b > c * l + d:
                k *= 2
                r = m
            elif a * r + b > c * r + d:
                k = k * 2 + 1
                l = m + 1
            else:
                return

    def query(self, x):
        k, l, r = 1, 0, self.n - 1
        res = -INF

        while True:
            if self.seg[k] is not None:
                a, b = self.seg[k]
                res = max(res, a * x + b)

            if l == r:
                return res

            m = (l + r) // 2

            if x <= m:
                k *= 2
                r = m
            else:
                k = k * 2 + 1
                l = m + 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)

used = [False] * N
sz = [0] * N
par = [-1] * N

ans = A[:]
best = [0] * N
sub = [0] * N


def get_centroid(s):
    order = [s]
    par[s] = -1

    for v in order:
        for u in G[v]:
            if used[u] or u == par[v]:
                continue
            par[u] = v
            order.append(u)

    for v in reversed(order):
        sz[v] = 1
        for u in G[v]:
            if not used[u] and par[u] == v:
                sz[v] += sz[u]

    n = len(order)

    for v in order:
        mx = n - sz[v]

        for u in G[v]:
            if not used[u] and par[u] == v:
                mx = max(mx, sz[u])

        if mx * 2 <= n:
            return v


# src の直線で dst を処理する単調 CHT
def apply(src, dst, c):
    hull = []

    # src は距離昇順なので、逆順なら傾き -d は昇順
    for v, p, d, b in reversed(src):
        k = -d

        if hull and hull[-1][0] == k:
            if hull[-1][1] >= b:
                continue
            hull.pop()

        while len(hull) >= 2:
            k1, b1 = hull[-2]
            k2, b2 = hull[-1]

            if (b1 - b2) * (k - k2) >= (b2 - b) * (k2 - k1):
                hull.pop()
            else:
                break

        hull.append((k, b))

    # c 自身も相方にできる
    k, b = 0, A[c]

    while len(hull) >= 2:
        k1, b1 = hull[-2]
        k2, b2 = hull[-1]

        if (b1 - b2) * (k - k2) >= (b2 - b) * (k2 - k1):
            hull.pop()
        else:
            break

    hull.append((k, b))

    j = 0

    for v, p, x, b in dst:
        while (
            j + 1 < len(hull)
            and hull[j][0] * x + hull[j][1]
            <= hull[j + 1][0] * x + hull[j + 1][1]
        ):
            j += 1

        best[v] = hull[j][0] * x + hull[j][1]


def solve(s):
    c = get_centroid(s)

    comps = []
    max_d = 0

    # BFS なので各成分は距離昇順
    for root in G[c]:
        if used[root]:
            continue

        cur = []
        q = deque([(root, c, 1, A[c] + A[root])])

        while q:
            v, p, d, sm = q.popleft()

            b = sm - d * (d + 1) // 2
            cur.append((v, p, d, b))
            max_d = max(max_d, d)

            for u in G[v]:
                if used[u] or u == p:
                    continue
                q.append((u, v, d + 1, sm + A[u]))

        comps.append(cur)

    k = len(comps)

    if k == 1:
        for v, p, d, b in comps[0]:
            best[v] = A[c]

    elif k == 2:
        apply(comps[0], comps[1], c)
        apply(comps[1], comps[0], c)

    elif k >= 3:
        cht = LiChao(max_d + 1)
        cht.add(0, A[c])

        for cur in comps:
            for v, p, d, b in cur:
                best[v] = cht.query(d)

            for v, p, d, b in cur:
                cht.add(-d, b)

        cht = LiChao(max_d + 1)
        cht.add(0, A[c])

        for cur in reversed(comps):
            for v, p, d, b in cur:
                best[v] = max(best[v], cht.query(d))

            for v, p, d, b in cur:
                cht.add(-d, b)

    best_c = A[c]

    for cur in comps:
        for v, p, d, b in cur:
            sub[v] = b - A[c] + best[v]
            best_c = max(best_c, sub[v])

        # 部分木最大値
        for v, p, d, b in reversed(cur):
            ans[v] = max(ans[v], sub[v])

            if p != c:
                sub[p] = max(sub[p], sub[v])

    ans[c] = max(ans[c], best_c)

    used[c] = True

    for u in G[c]:
        if not used[u]:
            solve(u)


solve(0)

print(min(ans))