結果

問題 No.1215 都市消滅ビーム
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:33:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,198 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 308,580 KB
最終ジャッジ日時 2025-03-20 20:34:32
合計ジャッジ時間 9,750 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import deque

sys.setrecursionlimit(1 << 25)

def main():
    N, K = map(int, stdin.readline().split())
    C = list(map(int, stdin.readline().split()))
    D = list(map(int, stdin.readline().split()))
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        edges[a].append(b)
        edges[b].append(a)
    
    LOG = 20
    parent = [[-1] * (N + 1) for _ in range(LOG)]
    depth = [0] * (N + 1)
    q = deque([1])
    visited = [False] * (N + 1)
    visited[1] = True
    while q:
        u = q.popleft()
        for v in edges[u]:
            if not visited[v]:
                visited[v] = True
                parent[0][v] = u
                depth[v] = depth[u] + 1
                q.append(v)
    
    for k in range(1, LOG):
        for v in range(1, N + 1):
            if parent[k-1][v] != -1:
                parent[k][v] = parent[k-1][parent[k-1][v]]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        for k in range(LOG-1, -1, -1):
            if parent[k][u] != -1 and depth[parent[k][u]] >= depth[v]:
                u = parent[k][u]
        if u == v:
            return u
        for k in range(LOG-1, -1, -1):
            if parent[k][u] != -1 and parent[k][u] != parent[k][v]:
                u = parent[k][u]
                v = parent[k][v]
        return parent[0][u]
    
    pre_sum = [0] * (K + 2)
    pre_LCA = [0] * (K + 2)
    pre_sum[0] = 0
    pre_LCA[0] = -1
    
    current_LCA = -1
    current_sum = 0
    for i in range(1, K + 1):
        c = C[i-1]
        if pre_LCA[i-1] == -1:
            current_LCA = c
        else:
            current_LCA = lca(pre_LCA[i-1], c)
        current_sum += D[i-1]
        pre_LCA[i] = current_LCA
        pre_sum[i] = current_sum
    
    suf_sum = [0] * (K + 2)
    suf_LCA = [0] * (K + 2)
    suf_sum[K+1] = 0
    suf_LCA[K+1] = -1
    
    current_LCA = -1
    current_sum = 0
    for i in range(K, 0, -1):
        c = C[i-1]
        if suf_LCA[i+1] == -1:
            current_LCA = c
        else:
            current_LCA = lca(c, suf_LCA[i+1])
        current_sum += D[i-1]
        suf_LCA[i] = current_LCA
        suf_sum[i] = current_sum
    
    X_values = []
    
    non_op_S = pre_sum[K]
    non_op_T = pre_LCA[K]
    if non_op_T == -1:
        X_non_op = -10**10
    else:
        X_non_op = non_op_S + depth[non_op_T]
    X_values.append(X_non_op)
    
    for a in range(0, K + 1):
        for b in range(a + 2, K + 2):
            sum_S = pre_sum[a] + suf_sum[b]
            lca_a = pre_LCA[a] if a != 0 else -1
            lca_b = suf_LCA[b] if b != K+1 else -1
            if lca_a == -1 and lca_b == -1:
                X = -10**10
            elif lca_a == -1:
                X = sum_S + depth[lca_b]
            elif lca_b == -1:
                X = sum_S + depth[lca_a]
            else:
                T = lca(lca_a, lca_b)
                X = sum_S + depth[T]
            X_values.append(X)
    
    X_values.sort()
    M = len(X_values)
    median_index = (M + 1) // 2 - 1
    print(X_values[median_index])

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