Day 179-Q3 — 2026-10-15 | 傾きが単調でない木の上の DP を、巻き戻し付き Li Chao 木で（挿入で書き換えた節点を記録し、DFS の帰りに戻す。Day178-Q3 の二分探索 CHT との速さと正しさの比較つき）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    S = [0] * (n + 1)
    C = [0] * (n + 1)
    adj = [[] for _ in range(n + 1)]
    pos = 1
    for v in range(1, n + 1):
        S[v] = int(data[pos]); C[v] = int(data[pos + 1]); pos += 2
    for _ in range(n - 1):
        u = int(data[pos]); v = int(data[pos + 1]); w = int(data[pos + 2]); pos += 3
        adj[u].append((v, w)); adj[v].append((u, w))
    # 根からの距離と DFS 順
    d = [0] * (n + 1)
    par = [0] * (n + 1)
    order = []
    st = [1]
    par[1] = -1
    while st:
        u = st.pop()
        order.append(u)
        for v, w in adj[u]:
            if v != par[u]:
                par[v] = u
                d[v] = d[u] + w
                st.append(v)
    xs = sorted(set(d[1:]))
    m = len(xs)
    idx = {x: i for i, x in enumerate(xs)}
    INF = 1 << 63
    size = 1
    while size < m:
        size <<= 1
    LA = [0] * (2 * size)          # 傾き
    LB = [INF] * (2 * size)        # 切片（INF = 直線なし）
    log = []                       # (節点, 元の傾き, 元の切片)

    def insert(a, b):
        node, l, r = 1, 0, size - 1
        while True:
            mid = (l + r) >> 1
            ca, cb = LA[node], LB[node]
            xm = xs[mid] if mid < m else xs[-1]
            if a * xm + b < ca * xm + cb:
                log.append((node, ca, cb))
                LA[node], LB[node] = a, b
                a, b, ca, cb = ca, cb, a, b
            if l == r or b >= INF:
                return
            xl = xs[l] if l < m else xs[-1]
            if a * xl + b < ca * xl + cb:
                node, r = 2 * node, mid
            else:
                xr = xs[r] if r < m else xs[-1]
                if a * xr + b < ca * xr + cb:
                    node, l = 2 * node + 1, mid + 1
                else:
                    return

    def query(i):
        x = xs[i]
        node, l, r = 1, 0, size - 1
        best = INF
        while True:
            val = LA[node] * x + LB[node]
            if val < best:
                best = val
            if l == r:
                return best
            mid = (l + r) >> 1
            if i <= mid:
                node, r = 2 * node, mid
            else:
                node, l = 2 * node + 1, mid + 1

    dp = [0] * (n + 1)
    # 反復 DFS：入るときに問い合わせと挿入、出るときに巻き戻し
    stack = [(1, 0)]
    while stack:
        u, mark = stack.pop()
        if mark < 0:               # 出る：log を長さ ~mark まで戻す
            keep = ~mark
            while len(log) > keep:
                node, ca, cb = log.pop()
                LA[node] = ca; LB[node] = cb
            continue
        if u != 1:
            dp[u] = query(idx[d[u]]) + S[u]
        keep = len(log)
        insert(C[u], dp[u] - C[u] * d[u])
        stack.append((u, ~keep))
        for v, w in adj[u]:
            if v != par[u]:
                stack.append((v, 0))
    sys.stdout.write("\n".join(map(str, dp[2:])) + "\n")


main()