Day 178-Q3 — 2026-10-14 | 木の上の凸包トリック（根へ向かう伝令の DP。DFS の行きで 1 か所だけ上書きし帰りで戻す「二分探索で挿入」の CHT。末尾から pop する CHT はほうき型の木で O(N^2) になる）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    adj = [[] for _ in range(n + 1)]
    p = 1
    for _ in range(n - 1):
        u, v, w = int(data[p]), int(data[p + 1]), int(data[p + 2])
        p += 3
        adj[u].append((v, w))
        adj[v].append((u, w))
    S = [0, 0]
    V = [0, 0]
    for _ in range(n - 1):
        S.append(int(data[p]))
        V.append(int(data[p + 1]))
        p += 2
    dist = [0] * (n + 1)
    dp = [0] * (n + 1)
    # 凸包は「祖先の直線 y = dp[j] - dist[j]*x」を傾きの降順に並べた配列。長さ top
    HD = [0] * (n + 1)            # 傾きの符号を反転した値 dist[j]
    HB = [0] * (n + 1)            # 切片 dp[j]
    HD[0], HB[0] = 0, 0           # 首都の直線
    top = 1
    # 反復 DFS。戻るときに (上書きした位置, 元の直線, 元の top) を書き戻す
    stack = [(1, 0, 0)]           # (頂点, 親, 状態 0=入る/1=出る)
    saved = {}
    while stack:
        v, par, state = stack.pop()
        if state == 1:
            pos, od, ob, otop = saved.pop(v)
            HD[pos], HB[pos] = od, ob
            top = otop
            continue
        if v != 1:
            d = dist[v]
            x = V[v]
            # 最小値の直線を二分探索: 値は添字について下に凸
            lo, hi = 0, top - 1
            while lo < hi:
                m = (lo + hi) >> 1
                if HB[m] - HD[m] * x >= HB[m + 1] - HD[m + 1] * x:
                    lo = m + 1
                else:
                    hi = m
            val = S[v] + x * d + HB[lo] - HD[lo] * x
            dp[v] = val
            # 挿入位置を二分探索: 最初に「新しい直線に負ける」位置 k (1<=k<top)
            lo, hi = 1, top
            while lo < hi:
                m = (lo + hi) >> 1
                d1, b1 = HD[m - 1], HB[m - 1]
                # m 番目が不要 ⇔ (b_new-b1)(d_m-d1) <= (b_m-b1)(d_new-d1)
                if (val - b1) * (HD[m] - d1) <= (HB[m] - b1) * (d - d1):
                    hi = m
                else:
                    lo = m + 1
            pos = lo
            saved[v] = (pos, HD[pos], HB[pos], top)
            HD[pos], HB[pos] = d, val
            top = pos + 1
            stack.append((v, par, 1))
        for u, w in adj[v]:
            if u != par:
                dist[u] = dist[v] + w
                stack.append((u, v, 0))
    print(" ".join(map(str, dp[2:])))


main()