結果

問題 No.3189 Semifinal Stage
コンテスト
ユーザー Mitarushi
提出日時 2025-06-15 17:18:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,274 ms / 4,000 ms
コード長 2,231 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 322,396 KB
最終ジャッジ日時 2025-06-19 22:30:56
合計ジャッジ時間 58,983 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

cut_mark = [False] * n

def find_centroid(v, p, total):
    s = 1
    cs_list = []
    for u in graph[v]:
        if u == p or cut_mark[u]:
            continue
        cs, c = find_centroid(u, v, total)
        if c is not None:
            return 0, c
        s += cs
        cs_list.append((u, cs))
    if total - s <= total // 2:
        if p != -1:
            cs_list.append((p, total - s))
        return 0, (v, cs_list)
    return s, None

c_dist = [[] for _ in range(n)]
def set_dist(c):
    queue = [(c, -1, 0)]
    c_dist[c].append((c, 0))
    for v, p, d in queue:
        for u in graph[v]:
            if u == p or cut_mark[u]:
                continue
            c_dist[u].append((c, d + 1))
            queue.append((u, v, d + 1))

def decompose(v, total):
    _, (c, cs_list) = find_centroid(v, -1, total)
    cut_mark[c] = True
    set_dist(c)
    for u, s in cs_list:
        decompose(u, s)

decompose(0, n)

class RemoveablePriorityQueue:
    def __init__(self):
        self.data = []
        self.count = {}
    
    def push(self, x):
        heappush(self.data, x)
        self.count[x] = self.count.get(x, 0) + 1

    def remove(self, x):
        self.count[x] -= 1
    
    def top(self):
        while self.data:
            x = self.data[0]
            if self.count[x] > 0:
                return x
            heappop(self.data)
        return None

black_pq = [RemoveablePriorityQueue() for _ in range(n)]
color = [0] * n

q = int(input())
for _ in range(q):
    t, v = map(int, input().split())
    v -= 1

    if t == 1:
        if color[v] == 0:
            for c, d in c_dist[v]:
                black_pq[c].push(d)
        else:
            for c, d in c_dist[v]:
                black_pq[c].remove(d)
        color[v] = 1 - color[v]
    else:
        ans = n
        for c, d in c_dist[v]:
            top = black_pq[c].top()
            if top is not None:
                ans = min(ans, d + top)
        print(ans)
0