树上好点问题 - 算法解析与 Python 实现

树上好点问题 - 算法解析与 Python 实现

问题描述

给定一棵树，其 N 个顶点的编号为 1 到 N 。第 i 条边连接顶点 A[i] 和顶点 B[i] 。顶点 i 的颜色为 C[i] 。如果从顶点 1 到顶点 x 的路径上（最短路径），不包含与点 x 相同颜色的点（顶点 x 本身除外），我们称顶点 x 为好点。按照升序输出所有好点。

输入

第一行输入一个正整数 N，表示顶点的数量。 第二行输入 N 个正整数 C[i]，分别表示每个点的颜色。 之后 N-1 行，每行输入两个正整数 A[i],B[i] 表示一条树边。 其中2≤N≤1e5，1≤C[i]≤1e5，保证给定的图是一棵树。

输出

输出使用换行符作为分隔符，按升序输出所有好点的编号。

样例输入

6 2 7 1 8 2 8 1 2 3 6 3 2 4 3 2 5

样例输出

1 2 3 4 6

数据范围限制

对于17%的数据， 2 ≤ N ≤ 10 ； 对于33%的数据， 2 ≤ N ≤ 3000 ； 对于100%的数据， 2 ≤ N ≤ 10^5 ,1 ≤ C[i] ≤ 10^5 ,1 ≤ A[i],B[i] ≤ N ，保证给定的图是一棵树。

解题思路

1. 首先构建树的邻接表表示，使用一个列表adj_list来存储每个顶点的相邻顶点。
2. 创建一个列表good_points来存储所有好点的编号。
3. 从顶点1开始，进行深度优先遍历。对于每个顶点x，检查与x相邻的顶点中是否存在与x颜色相同的顶点，如果不存在，则将x添加到good_points列表中。
4. 最后对good_points列表进行升序排序，并按行输出。

具体实现

def dfs(x, parent, colors, adj_list, good_points):
    for neighbor in adj_list[x]:
        if neighbor != parent and colors[neighbor] == colors[x]:
            return
    good_points.append(x)
    for neighbor in adj_list[x]:
        if neighbor != parent:
            dfs(neighbor, x, colors, adj_list, good_points)

def find_good_points(N, colors, edges):
    adj_list = [[] for _ in range(N+1)]
    for a, b in edges:
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    good_points = []
    dfs(1, 0, colors, adj_list, good_points)
    good_points.sort()
    return good_points

# 读取输入
N = int(input())
colors = list(map(int, input().split()))
edges = []
for _ in range(N-1):
    a, b = map(int, input().split())
    edges.append((a, b))

# 调用函数并输出结果
result = find_good_points(N, colors, edges)
for point in result:
    print(point)

复杂度分析

• 时间复杂度：O(N)，遍历所有顶点和边。
• 空间复杂度：O(N)，使用了邻接表和good_points列表。