今天更新的是广联达0913秋招笔试真题中的一题。
作者：猛哥
题目描述
小明在梦中困在一个迷宫里了。迷宫太难了，小明发动特殊能力让迷宫变得简单起来。迷宫变成了一张有n个节点的有根树（根为1号节点）的结构，只能在一个节点往其儿子节点走，而当没有导向其他节点的路径存在时，即该节点没有儿子节点时，便走出了迷宫。这样一来，小明只要沿着任意可以走的路径行进就肯定可以到达出口了！出发前为了做好周密准备，小明想知道处于这个迷宫的各个位置能到哪些出口。
输入描述
第一行3个整数分别为n,m和q表示迷宫节点数量，迷宫路径数量和询问数量。
第二行m个整数u1, u2, ``...``, um
第三行m个整数v1, v2, ..., vm
其中ui, vi代表第i条有向路径为从节点ui通往节点vi，即节点ui有一个儿子节点vi。保证形成一棵以1号节点为根的有根树。
第四行q个整数a1, a2, ..., aq。表示第i次询问为：若处于ai节点，可能到达多少个不同的出口？注意，若一个节点没有导向其他节点的路径存在时，即没有儿子节点时，这个节点则为一个出口。
1`` ``<=`` ``n,`` ``m,`` ``q`` ``<=`` ``50000, 1`` ``<=`` ``ui, vi`` ``<=`` ``n, ui != vi
输出描述
输出一行q个整数，分别表示每次询问的答案。
样例输入
输入
代码语言：javascript复制3 2 3
1 1
2 3
1 2 3
输出
代码语言：javascript复制2 1 1
提示
节点1可以走向节点2和节点3，并不是出口。节点2和节点3都没有导向其他节点的路径了，均为出口。若处于节点1，可以走向节点2或节点3，有2种可能的出口。若处于节点2，只有节点2本身一个出口；节点3同理
题目解析
本题其实是求以u为根节点的子树中的叶子节点的数目。
令ans[u]为以u为根节点的子树中的叶子节点的数目，显然ans[u] = ans[v1] ans[v2] ans[vk]，其中v1, v2, ..., vk为u的所有的子节点。而当u没有节点时，ans[u] = 1。我们可以直接通过一次DFS预处理出ans数组，对于每次查询直接输出答案即可，时间复杂度为O(n)。
代码
Python
代码语言：javascript复制# 作者：闭着眼睛学数理化
# 算法训练营咨询微信：278166530
from collections import defaultdict
def dfs(neighbor_dic, leaf_num_dic, node):
# 递归终止条件：
# 如果node是一个叶节点，即其不包含任何子节点
# 将leaf_num_dic中的node储存为1
# 则返回1，表示只包含一个叶节点，仅有一个出口
if len(neighbor_dic[node]) == 0:
leaf_num_dic[node] = 1
return 1
# 若node不是一个叶节点，则遍历其所有子节点child_node
# 对子节点child_node进行dfs递归调用，
# 计算每一个子节点所包含的叶节点个数
# 将结果存入child_num变量中
leaf_num = 0
for child_node in neighbor_dic[node]:
leaf_num = dfs(neighbor_dic, leaf_num_dic, child_node)
# leaf_num存入leaf_num_dic中
leaf_num_dic[node] = leaf_num
# 返回leaf_num，用于上一层父节点的计算
return leaf_num
# 输入节点个数n，边的个数m，询问数量q
n, m, q = map(int, input().split())
# 输入父节点列表和子节点列表
parent_list = list(map(int, input().split()))
children_list = list(map(int, input().split()))
# 输入询问列表
q_list = list(map(int, input().split()))
# 根据父节点列表和子节点列表，构建用哈希表表示的邻接表neighbor_dic
neighbor_dic = defaultdict(list)
for p, c in zip(parent_list, children_list):
neighbor_dic[p].append(c)
# 构建一个哈希表，用于储存每一个节点下面的节点数
# key为节点的值，value为该节点下面的节点数
leaf_num_dic = dict()
# 递归调用入口，根节点是1
dfs(neighbor_dic, leaf_num_dic, 1)
# 对于q_list中的每一个node，在哈希表leaf_num_dic中找到其下面叶节点的个数
ans = [leaf_num_dic[node] for node in q_list]
# 输出答案
print(" ".join(str(num) for num in ans))
