Day 180-Q2 — 2026-10-16 | 距離の上限つき祖先からの木 DP（NOI2014「購票」と同じ形と記憶）を、深さのセグメント木の各節点に凸包を持たせて巻き戻す

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0] * (n + 1)
    W = [0] * (n + 1)
    P = [0] * (n + 1)
    Q = [0] * (n + 1)
    Lim = [0] * (n + 1)
    ch = [[] for _ in range(n + 1)]
    pos = 1
    for v in range(2, n + 1):
        f, s, p, q, l = (int(data[pos + i]) for i in range(5))
        pos += 5
        par[v] = f; W[v] = s; P[v] = p; Q[v] = q; Lim[v] = l
        ch[f].append(v)
    # 深さ（頂点数）の最大を求めてセグ木の大きさを決める
    dep = [0] * (n + 1)
    order = [1]
    for u in order:
        for v in ch[u]:
            dep[v] = dep[u] + 1
            order.append(v)
    H = max(dep) + 1
    size = 1
    while size < H:
        size <<= 1
    HA = [[] for _ in range(2 * size)]   # 節点ごとの凸包：傾き（-D_u、追加順に減少）
    HB = [[] for _ in range(2 * size)]   # 切片 dp_u
    TOP = [0] * (2 * size)
    log = []                              # (節点, 位置, 元の傾き, 元の切片, 元の top)
    pathD = [0] * H                       # 根からの道：深さ i の頂点の D
    D = [0] * (n + 1)
    dp = [0] * (n + 1)

    def insert(k, a, b):
        node = size + k
        while node:
            A = HA[node]; B = HB[node]; t = TOP[node]
            # 末尾から不要になる直線を二分探索で：位置 p の直線が (p-1, 新) に挟まれて不要か
            lo, hi = 1, t
            while lo < hi:
                mid = (lo + hi) >> 1
                a1 = A[mid - 1]; b1 = B[mid - 1]
                if (b - b1) * (a1 - A[mid]) <= (B[mid] - b1) * (a1 - a):
                    hi = mid
                else:
                    lo = mid + 1
            p = lo if t > 0 else 0
            if p < len(A):
                log.append((node, p, A[p], B[p], t))
                A[p] = a; B[p] = b
            else:
                log.append((node, p, None, None, t))
                A.append(a); B.append(b)
            TOP[node] = p + 1
            node >>= 1

    def hull_min(node, x):
        A = HA[node]; B = HB[node]
        lo, hi = 0, TOP[node] - 1
        while lo < hi:
            mid = (lo + hi) >> 1
            if A[mid] * x + B[mid] <= A[mid + 1] * x + B[mid + 1]:
                hi = mid
            else:
                lo = mid + 1
        return A[lo] * x + B[lo]

    def query(l, r, x):            # 深さ添字 [l, r] の直線の x での最小
        best = None
        l += size; r += size + 1
        while l < r:
            if l & 1:
                v = hull_min(l, x)
                if best is None or v < best:
                    best = v
                l += 1
            if r & 1:
                r -= 1
                v = hull_min(r, x)
                if best is None or v < best:
                    best = v
            l >>= 1; r >>= 1
        return best

    # 反復 DFS：入るとき計算して挿入、出るとき巻き戻す
    stack = [1]
    while stack:
        u = stack.pop()
        if u < 0:
            keep = ~u
            while len(log) > keep:
                node, p, a, b, t = log.pop()
                if a is None:
                    HA[node].pop(); HB[node].pop()
                else:
                    HA[node][p] = a; HB[node][p] = b
                TOP[node] = t
            continue
        k = dep[u]
        if u != 1:
            D[u] = D[par[u]] + W[u]
            # D_u - D_anc <= Lim[u] となる最も浅い深さ添字を二分探索
            need = D[u] - Lim[u]
            lo, hi = 0, k - 1
            while lo < hi:
                mid = (lo + hi) >> 1
                if pathD[mid] >= need:
                    hi = mid
                else:
                    lo = mid + 1
            dp[u] = query(lo, k - 1, P[u]) + P[u] * D[u] + Q[u]
        pathD[k] = D[u]
        stack.append(~len(log))
        insert(k, -D[u], dp[u])
        stack.extend(ch[u])
    sys.stdout.write("\n".join(map(str, dp[2:])) + "\n")


main()