結果

問題 No.1215 都市消滅ビーム
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:49:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,369 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 101,516 KB
最終ジャッジ日時 2025-06-12 18:49:27
合計ジャッジ時間 9,156 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 11 WA * 2 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0

    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1

    C = list(map(int, data[idx:idx+K]))
    idx += K
    D = list(map(int, data[idx:idx+K]))
    idx += K

    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a = int(data[idx])
        b = int(data[idx+1])
        idx += 2
        edges[a].append(b)
        edges[b].append(a)

    parent = [0]*(N+1)
    depth = [0]*(N+1)
    visited = [False]*(N+1)
    stack = [(1, 0)]
    while stack:
        u, p = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        parent[u] = p
        for v in edges[u]:
            if not visited[v]:
                depth[v] = depth[u] + 1
                stack.append((v, u))

    def lca(u, v):
        while u != v:
            if depth[u] > depth[v]:
                u = parent[u]
            else:
                v = parent[v]
        return u

    pre_lca = [0]*(K+1)
    pre_lca[0] = 0
    for i in range(1, K+1):
        if i == 1:
            pre_lca[i] = C[i-1]
        else:
            pre_lca[i] = lca(pre_lca[i-1], C[i-1])

    suf_lca = [0]*(K+2)
    suf_lca[K+1] = 0
    for i in range(K, 0, -1):
        if i == K:
            suf_lca[i] = C[i-1]
        else:
            suf_lca[i] = lca(suf_lca[i+1], C[i-1])

    pre_sum = [0]*(K+1)
    for i in range(1, K+1):
        pre_sum[i] = pre_sum[i-1] + D[i-1]

    S_total = pre_sum[K]

    X_values = []
    X_values.append(S_total + depth[pre_lca[K]])

    for l in range(1, K+1):
        for r in range(l, K+1):
            if l == 1 and r == K:
                continue
            if l == 1:
                u = suf_lca[r+1]
            elif r == K:
                u = pre_lca[l-1]
            else:
                a = pre_lca[l-1]
                b = suf_lca[r+1]
                u = lca(a, b)
            sum_remaining = S_total - (pre_sum[r] - pre_sum[l-1])
            if sum_remaining == 0:
                X = -10**18
            else:
                X = sum_remaining + depth[u]
            X_values.append(X)

    X_values.append(-10**18)

    X_values.sort()
    m = (len(X_values) + 1) // 2
    print(X_values[m-1])

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