对于给定的无向无根树,第 个节点上有一个权值 。我们定义一条简单路径是好的,当且仅当:路径上的点的点权最小值小于等于 ,路径上的点的点权最大值大于等于 。 保证给定的 ,你需要计算有多少条简单路径是好的。
区块链毕设网qklbishe.com为您提供问题的解答
对于给定的无向无根树,第
个节点上有一个权值
。我们定义一条简单路径是好的,当且仅当:路径上的点的点权最小值小于等于
,路径上的点的点权最大值大于等于
。
保证给定的
,你需要计算有多少条简单路径是好的。
为啥使用深度优先搜索只能通过示例和一个例子
line = [int(item) for item in input().split(" ")] node_num = line[0] min_num = line[1] max_num = line[2] node_val = [int(item) for item in input().split(" ")] node_tu = [[0] * node_num for i in range(node_num)] for i in range(0, node_num - 1): line = [int(item) for item in input().split(" ")] node_tu[line[0]-1][line[1]-1] = 1 node_tu[line[1]-1][line[0]-1] = 1 # print(node_tu) resa = [] def get_next_path(node_tu, searched_path): node = searched_path[-1] res = [] for i in range(node_num): if node_tu[node - 1][i] == 1 and i + 1 not in searched_path: res.append(i + 1) return res def search_path(node_tu, searched_path, res): next_path = get_next_path(node_tu, searched_path) if not next_path: val_list = [] for item in searched_path: val_list.append(node_val[item - 1]) if min(val_list) <= min_num and max(val_list) >= max_num: temp = list(reversed(searched_path)) if searched_path not in res and temp not in res: res.append(searched_path) else: for node in next_path: search_path(node_tu, searched_path + [node], res) for node in range(1,node_num+1): search_path(node_tu, [node,], resa) print(len(resa))
23:03
以上就是关于问题对于给定的无向无根树,第 个节点上有一个权值 。我们定义一条简单路径是好的,当且仅当:路径上的点的点权最小值小于等于 ,路径上的点的点权最大值大于等于 。
保证给定的 ,你需要计算有多少条简单路径是好的。的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训