結果

問題 No.1197 モンスターショー
ユーザー gew1fw
提出日時 2025-06-12 20:43:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,567 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 53,940 KB
最終ジャッジ日時 2025-06-12 20:43:44
合計ジャッジ時間 6,305 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 7 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left

sys.setrecursionlimit(1 << 25)

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

    N = int(data[ptr])
    ptr += 1
    K = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1

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

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

    LOG = 20
    parent = [[-1] * (N + 1) for _ in range(LOG)]
    depth = [0] * (N + 1)
    in_time = [0] * (N + 1)
    out_time = [0] * (N + 1)
    time = 0

    def dfs(u, p):
        nonlocal time
        in_time[u] = time
        time += 1
        parent[0][u] = p
        for v in edges[u]:
            if v != p:
                depth[v] = depth[u] + 1
                dfs(v, u)
        out_time[u] = time - 1

    dfs(1, -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]]
            else:
                parent[k][v] = -1

    def lca(u, v):
        if in_time[u] > in_time[v]:
            u, v = v, u
        if in_time[v] <= in_time[u] <= out_time[u]:
            return u
        for k in range(LOG-1, -1, -1):
            if parent[k][u] != -1 and in_time[parent[k][u]] > in_time[v]:
                u = parent[k][u]
        return parent[0][u]

    slimes = C.copy()
    sum_depth_c = sum(depth[c] for c in slimes)

    for _ in range(Q):
        query = data[ptr]
        ptr += 1
        if query == '1':
            p = int(data[ptr]) - 1
            ptr += 1
            d = int(data[ptr])
            ptr += 1
            old = slimes[p]
            sum_depth_c -= depth[old]
            slimes[p] = d
            sum_depth_c += depth[d]
        else:
            e = int(data[ptr])
            ptr += 1
            sum_lca = 0
            u = e
            prev = -1
            while u != -1:
                sum_lca += depth[u]
                u = parent[0][u]
            sum_lca = 0
            u = e
            while u != -1:
                cnt_u = 0
                for c in slimes:
                    if in_time[u] <= in_time[c] <= out_time[u]:
                        cnt_u += 1
                sum_lca += depth[u] * cnt_u
                u = parent[0][u]
            total = sum_depth_c + K * depth[e] - 2 * sum_lca
            print(total)

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