体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都坐了一个人,安全出口在树的根部,也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点可以同时容纳两个及以上的人,这就需要一种策略,来使得人群尽快疏散,问在采取最优策略的情况下,体育场最快可以在多长时间内疏散完成。
数据范围:
第一行包含一个正整数n,即树的结点数量。 接下来有n-1行,每行有两个正整数x,y,表示在x和y结点之间存在一条边。(1<=x,y<=n)
输出仅包含一个正整数,表示所需要的最短时间
6 2 1 3 2 4 3 5 2 6 1
4
from collections import defaultdict n = int(input()) d = defaultdict(set) for _ in range(n-1): a, b = map(int, input().split()) d[a].add(b) d[b].add(a) ''' def dfs(x, pre): # 写成递归会报错,只能过80% global res # dfs返回x及以下总结点数 total = 0 # total记录所有子节点的总节点数之和 for nxt in d[x]: # 对所有子节点递归 if nxt != pre: tmp = dfs(nxt, x) total += tmp if tmp > res: res = tmp # 题目最后答案为节点1所有子节点中总节点数的最大值 return 1 + total res = 0 dfs(1,-1) print(res) ''' res = 0 # 迭代法,输出res为1的所有子节点的树所含节点最大值 for nxt in d[1]: visited = set([1,nxt]) # 这里visited如果设置成数组[False]*(n+1),就会超时 q = [nxt] # dfs cnt = 0 # cnt记录每个子节点的树中节点总量 while q: cur = q.pop() cnt += 1 for i in d[cur]: if i not in visited: q.append(i) visited.add(i) if cnt > res: res = cnt print(res)