結果

問題 No.417 チューリップバブル
ユーザー lam6er
提出日時 2025-03-20 20:52:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 4,738 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 78,188 KB
最終ジャッジ日時 2025-03-20 20:52:40
合計ジャッジ時間 4,913 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    U = [int(sys.stdin.readline()) for _ in range(N)]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B, C = map(int, sys.stdin.readline().split())
        edges[A].append((B, C))
        edges[B].append((A, C))
    
    parent = [None] * N
    children = [[] for _ in range(N)]
    stack = [0]
    visited = [False] * N
    visited[0] = True
    while stack:
        u = stack.pop()
        for v, c in edges[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = (u, c)
                children[u].append((v, c))
                stack.append(v)
    
    post_order = []
    visited = [False] * N
    stack = [(0, False)]
    while stack:
        u, done = stack.pop()
        if done:
            post_order.append(u)
            continue
        visited[u] = True
        stack.append((u, True))
        for v, c in reversed(children[u]):
            if not visited[v]:
                stack.append((v, False))
    
    dp_case_b = [defaultdict(int) for _ in range(N)]
    
    for u in post_order:
        if u == 0:
            current_dp = defaultdict(int)
            current_dp[0] = 0
            for v, c_edge in children[u]:
                child_dp = dp_case_b[v]
                new_current = defaultdict(int)
                for cost in current_dp:
                    current_u = current_dp[cost]
                    for c_cost in child_dp:
                        c_u = child_dp[c_cost]
                        total_cost = cost + c_cost
                        if total_cost > M:
                            continue
                        if new_current[total_cost] < current_u + c_u:
                            new_current[total_cost] = current_u + c_u
                for cost in new_current:
                    if new_current[cost] > current_dp.get(cost, 0):
                        current_dp[cost] = new_current[cost]
                for cost in child_dp:
                    c_u = child_dp[cost]
                    if cost <= M and c_u > current_dp.get(cost, 0):
                        current_dp[cost] = c_u
            add_u = U[u]
            new_current = defaultdict(int)
            for cost in current_dp:
                new_u = current_dp[cost] + add_u
                if new_u > new_current.get(cost, 0):
                    new_current[cost] = new_u
            for cost in new_current:
                if new_current[cost] > current_dp.get(cost, 0):
                    current_dp[cost] = new_current[cost]
            dp_case_b[u] = current_dp
        else:
            p, c_edge = parent[u]
            edge_cost = c_edge * 2
            current_dp = defaultdict(int)
            current_dp[edge_cost] = 0
            for v, c_child in children[u]:
                child_dp = dp_case_b[v]
                new_current = defaultdict(int)
                for cost in current_dp:
                    current_u = current_dp[cost]
                    for c_cost in child_dp:
                        c_u = child_dp[c_cost]
                        total_cost = cost + c_cost
                        if total_cost > M:
                            continue
                        if new_current[total_cost] < current_u + c_u:
                            new_current[total_cost] = current_u + c_u
                for cost in new_current:
                    if new_current[cost] > current_dp.get(cost, 0):
                        current_dp[cost] = new_current[cost]
                for cost in child_dp:
                    c_u = child_dp[cost]
                    total_cost = edge_cost + cost
                    if total_cost > M:
                        continue
                    if (current_dp.get(total_cost, 0)) < current_dp.get(edge_cost, 0) + c_u:
                        current_dp[total_cost] = current_dp[edge_cost] + c_u
            add_u = U[u]
            new_current = defaultdict(int)
            for cost in current_dp:
                new_u = current_dp[cost] + add_u
                new_cost = cost
                if new_cost > M:
                    continue
                if new_u > new_current.get(new_cost, 0):
                    new_current[new_cost] = new_u
            for cost in new_current:
                if new_current[cost] > current_dp.get(cost, 0):
                    current_dp[cost] = new_current[cost]
            dp_case_b[u] = current_dp
    
    max_u = 0
    root_dp = dp_case_b[0]
    for cost in root_dp:
        if cost <= M and root_dp[cost] > max_u:
            max_u = root_dp[cost]
    print(max_u)

if __name__ == "__main__":
    main()
0