题解 | 在树上游玩

from sys import stdin
from collections import defaultdict


# 计算从某个被标记的节点出发，不需要染色就能够到达的未被标记节点的数量
def dfs(node, parent):  # (当前访问的节点， 当前节点的父节点)
    visited[node] = 1
    cnt = 0
    for neighbor in tree[node]:
        if not marked[neighbor]:
            cnt += 1
        elif neighbor != parent:
            cnt += dfs(neighbor, node)
    return cnt


while True:
    try:
        input = stdin.read
        data = list(map(int, input().split()))
        n = data[0]
        k = data[1]
        tree = defaultdict(list)  # tree[i]表示节点i的相邻节点
        marked = [0] * n  # marked[i] 表示节点i是否被标记
        MOD = 10 ** 9 + 7
        cnt = []

        for i in range(2, k + 2):   # 读取被标记的节点
            marked[data[i] - 1] = 1

        for j in range(k + 2, 2 * n + k, 2):    # 构建节点的邻接表
            u = data[j] - 1
            v = data[j + 1] - 1
            tree[u].append(v)
            tree[v].append(u)

        visited = [0] * n   # 记录节点是否被访问过
        count = 0       # 记录需要额外染色的被标记节点的数量
        ways = 1    # 满足条件的染色方案的数量

        # 遍历所有标记的节点
        for i in range(n):
            if marked[i] and not visited[i]:    # 避免重复
                count += 1
                # 每个未被访问的被标记节点需要额外染色一条边，所以count即为需要染色的边数
                ways = (ways * dfs(i, -1)) % MOD
                # 对于每个未被访问的被标记节点，它能到达多少个未被标记节点，就有多少种染色方案。

        print(count, ways)
    except:
        break