結果

問題 No.1215 都市消滅ビーム
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:40:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,262 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 345,976 KB
最終ジャッジ日時 2025-03-31 17:41:55
合計ジャッジ時間 9,734 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, K = int(data[idx]), int(data[idx+1])
    idx +=2
    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, b = int(data[idx]), int(data[idx+1])
        edges[a].append(b)
        edges[b].append(a)
        idx +=2
    
    LOG = 20
    parent = [[-1]*(N+1) for _ in range(LOG)]
    depth = [0]*(N+1)
    stack = [(1, -1, 0)]
    while stack:
        v, p, d = stack.pop()
        parent[0][v] = p
        depth[v] = d
        for u in edges[v]:
            if u != p:
                stack.append((u, v, d+1))
    
    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] != parent[k][v]:
                u = parent[k][u]
                v = parent[k][v]
        return parent[0][u]
    
    left_LCA = [ -1 ] * (K + 2)
    current_LCA = -1
    for l in range(2, K+2):
        if l-1 == 1:
            current_LCA = C[0]
        else:
            current_LCA = lca(current_LCA, C[l-2])
        left_LCA[l] = current_LCA
    
    right_LCA = [ -1 ] * (K +2)
    current_LCA = -1
    for r in range(K, 0, -1):
        if r == K:
            current_LCA = C[K-1]
        else:
            current_LCA = lca(current_LCA, C[r-1])
        right_LCA[r] = current_LCA
    
    total_D = sum(D)
    prefix = [0]*(K+1)
    for i in range(1, K+1):
        prefix[i] = prefix[i-1] + D[i-1]
    
    X_list = []
    optional_case = True
    l_full = K + 1
    if l_full <= K+1 and left_LCA[l_full] != -1:
        T = left_LCA[l_full]
        sum_S = total_D
        depth_T = depth[T]
        X = sum_S + depth_T
        X_list.append(X)
    
    for l in range(1, K+1):
        for r in range(l, K+1):
            if l == 1 and r == K:
                X = -10**10
                X_list.append(X)
                continue
            
            has_left = l > 1
            has_right = r < K
            
            T = -1
            if has_left and has_right:
                l_lca = left_LCA[l]
                r_lca = right_LCA[r+1]
                T = lca(l_lca, r_lca)
            elif has_left:
                T = left_LCA[l]
            elif has_right:
                T = right_LCA[r+1]
            else:
                assert False, "Should be handled by l ==1 and r==K case"
            
            sum_lr = prefix[r] - prefix[l-1]
            sum_S = total_D - sum_lr
            depth_T_val = depth[T]
            X = sum_S + depth_T_val
            X_list.append(X)
    
    M = K*(K+1)//2 +1
    X_list.sort()
    median_pos = (M +1) //2 -1
    print(X_list[median_pos])

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