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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:08:43
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,446 bytes
• コンパイル時間: 65 ms
• コンパイル使用メモリ: 82,600 KB
• 実行使用メモリ: 259,860 KB
• 最終ジャッジ日時: 2026-10-02 20:59:19
• 合計ジャッジ時間: 65,949 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 31 TLE * 8

ソースコード

INF = 10**30


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

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

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

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

        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:
            self.add(a, b, k * 2, l, m)
        elif a * r + b > c * r + d:
            self.add(a, b, k * 2 + 1, m + 1, r)

    def query(self, x, k=1, l=0, r=None):
        if r is None:
            r = self.n - 1

        line = self.seg[k]
        res = -INF if line is None else line[0] * x + line[1]

        if l == r:
            return res

        m = (l + r) // 2

        if x <= m:
            return max(res, self.query(x, k * 2, l, m))
        else:
            return max(res, self.query(x, k * 2 + 1, m + 1, r))


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 = []
    stack = [s]
    par[s] = -1

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

        for u in G[v]:
            if used[u] or u == par[v]:
                continue
            par[u] = v
            stack.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


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

    comps = []
    max_d = 0

    for root in G[c]:
        if used[root]:
            continue

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

        while stack:
            v, p, d, sm = stack.pop()

            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
                stack.append((u, v, d + 1, sm + A[u]))

        comps.append(cur)

    # 左から右
    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))