結果

問題 No.3189 Semifinal Stage
ユーザー Mitarushi
提出日時 2025-06-15 16:56:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,178 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 408,036 KB
最終ジャッジ日時 2025-06-19 19:15:05
合計ジャッジ時間 76,563 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop
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 get_size(v, p):
    s = 1
    for u in graph[v]:
        if u == p or cut_mark[u]:
            continue
        s += get_size(u, v)
    return s

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

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

def decompose(v):
    total = get_size(v, -1)
    _, c = find_centroid(v, -1, total)
    cut_mark[c] = True
    set_dist(c, -1, c, 0)
    for u in graph[c]:
        if cut_mark[u]:
            continue
        decompose(u)

decompose(0)

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