算法竞赛中的树和图

从构建出发

算法竞赛中，我们通常会遇到有关树形结构或图结构的问题，而如何有效地构建结构，利用好树和图的各种特点成为了解题的第一步。下文中我将给出恰当的方法来实现树和图中的基本操作。

例1： 给定一颗树，树根为\(1\)，每个点的点权为\(V_i\)，请实现这样的结构，使之可以遍历每个节点所在的深度，也可以遍历每个深度所有的节点

输入格式： 输入的第一行包括一个整数\(n\)。

第二行包含\(n-1\)个整数\(F_i\)，相邻整数间用一个空格分隔，分别表示第\(2\)至\(n\)个节点的父节点编号

第三行包含\(n\)个整数\(V_i\)，相邻整数之间使用一个空格分隔，分别表示每个节点的点权

代码如下：

n = int(input())
father = [0, 0] + list(map(int, input().split()))
values = [0] + list(map(int, input().split())) # 存每个节点的值
dep = [0] * (n + 1) # 每个节点的深度
dep_node = [[] for _ in range(n + 1)]   # 存每个深度的节点
deep_max = 0    # 深度的最大值

for i in range(1, n + 1):   # 求每个深度有哪些节点
    dep[i] = dep[father[i]] + 1 # 一个节点的深度是它父节点深度 + 1得到的，这样我们就递归地得到了每个节点的深度
    deep_max = max(deep_max, dep[i])    # 维护深度的最大值
    dep_node[dep[i]].append(i)  # i节点所在深度为dep[i],于是为dep_node的第dep[i]层添加i

这样我们就得到了数组\(fathers\), \(values\), \(dep\), \(dep\_node\)和整数\(deep\_max\),它们分别表示：

• 编号为\(i\)的节点的父节点\(fathers[i]\)
• 编号为\(i\)的节点的点权\(values[i]\)
• 编号为\(i\)的节点的深度\(dep[i]\)
• 深度为\(i\)的第\(j\)个节点\(dep\_node[i][j]\)
• 树的最大深度\(deep\_max\)

在得到这些基础属性后，我们就可以很方便地对树进行遍历等操作

在实际问题中，我们也会看到另一种树形结构的构筑，它的输入并没有直接告诉我们对于某个节点\(i\)，它的父节点是什么，而是类似图结构一样，告诉我们节点\(u\)和\(v\)之间存在一条边，对于这样的输入，我们可以用图的邻接表来构建恰当的树形结构。

例2：给定一颗有\(n\)个节点的有根树，其中节点\(i\)的点权为\(a_i\)，请设计一种结构，使我们可以得到每个点对应的深度

输入格式：输入的第一行包含两个正整数\(n,m\)，用一个空格分隔。

第二行包含\(n\)个整数\(a_1, a_2,...,a_n\),相邻整数之间使用一个空格分隔。

接下来\(n-1\)行，每行包含两个正整数\(u_i,v_i\),表示节点\(u_i\)和\(v_i\)之间有一条边

代码如下：

n, m = map(int, input().split())
values = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]  # 用邻接表存储节点与边的信息
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

dep = [0] * (n + 1)
dep[1] = 1

def depth(node, father):
    for children in g[node]:
        if children != father:
            dep[children] = dep[node] + 1
            depth(children, node)   # 递归地计算每个节点的深度

depth(1, 0)