QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#848377#9996. 辞甲猾扎cyc001TL 0ms0kbPython31.2kb2025-01-08 20:05:012025-01-08 20:05:06

Judging History

This is the latest submission verdict.

  • [2025-01-08 20:05:06]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-08 20:05:01]
  • Submitted

answer

from collections import deque, defaultdict

def min_white_nodes(n, k, black_nodes, edges):
    # 构建树的邻接表
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # 标记初始黑色节点
    is_black = [False] * (n + 1)
    for b in black_nodes:
        is_black[b] = True

    # 找出需要染白的最少点
    visited = [False] * (n + 1)
    queue = deque()
    white_count = 0

    # 多源 BFS,从黑色点出发
    for b in black_nodes:
        queue.append(b)
        visited[b] = True

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if is_black[node]:  # 黑色传播的点
                    is_black[neighbor] = True
                else:  # 灰色传播的点需要控制
                    white_count += 1
                queue.append(neighbor)
                visited[neighbor] = True

    return white_count

# 读取输入
n, k = map(int, input().split())
black_nodes = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]

# 求解
result = min_white_nodes(n, k, black_nodes, edges)
print(result)

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

1000000 250
4246 6001 15765 16292 18291 18607 20931 24218 25916 28742 34837 37283 38797 38805 45707 47625 47981 55382 60377 60815 61528 71455 73316 79270 81165 88222 93488 95638 99798 100415 100686 107252 107624 110367 116459 118365 121070 130962 131316 132856 141146 152992 153050 154652 156855 1669...

output:


result: