QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#848377 | #9996. 辞甲猾扎 | cyc001 | TL | 0ms | 0kb | Python3 | 1.2kb | 2025-01-08 20:05:01 | 2025-01-08 20:05:06 |
Judging History
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...