关注
n,m,d = map(int,input().split())
spec = [int(c) for c in input().split()]
lis = [int(c) for c in input().split()]
# nei为节点邻接表
nei = [[] for _ in range(n+1)]
for i in range(n-1):
nei[i+2].append(lis[i])
nei[lis[i]].append(i+2)
for i in range(1,n+1):
nei[i].append(i)
flag = [0] * (n+1)
for i in range(m):
dis = 1
queue = [spec[i]]
# 存储bfs遍历的节点
see = set()
while queue:
size = len(queue)
while size != 0 :
tmp = queue.pop(0)
for j in range(len(nei[tmp])):
if nei[tmp][j] not in see:
see.add(nei[tmp][j])
flag[nei[tmp][j]] += 1
for i in nei[tmp]:
if i != tmp:
queue.append(i)
size -= 1
dis += 1
if dis > d:
break
#共有多少合适的点
count = 0
for i in range(len(flag)):
if flag[i] == m:
count += 1
print(count) 我觉得这题是个无向图的题,和树关系好像不大,参考了邻接表 + bfs的方法 ,总的思路就是: 1、以各特殊点bfs展开,当bfs深度为大于d时,切换为下一个特殊点, 2、如此往复,便记录下每个节点总共被以特殊点为起点的节点遍历到的次数 3、如果遍历次数等于特殊节点数量,即为符合要求的节点
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
07-23 12:26
西南石油大学 光学工程师 点赞 评论 收藏
分享
06-19 22:53
江西应用科技学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 工作中哪个瞬间让你想离职 #
28324次浏览 195人参与
# 在职场上,你最讨厌什么样的同事 #
16210次浏览 159人参与
# 小米硬件提前批进度交流 #
171071次浏览 1527人参与
# 机械人,秋招第一次笔试的企业是哪家? #
41080次浏览 325人参与
# 哪些公司校招卡第一学历 #
73634次浏览 292人参与
# 选了这个offer,你有没有后悔? #
592896次浏览 4026人参与
# 入职以后才知道的校招谎言 #
88932次浏览 587人参与
# 华子oc时间线 #
1244924次浏览 6487人参与
# 哪些公司开提前批了? #
29448次浏览 274人参与
# 担心入职之后被发现很菜怎么办 #
139123次浏览 808人参与
# 风评不好的公司,你会去吗? #
65491次浏览 459人参与
# Offer比较,你最看重什么? #
192080次浏览 1309人参与
# 实习如何「偷」产出? #
55118次浏览 1384人参与
# 两会劳动法放大招 #
76678次浏览 692人参与
# 不卡学历的大厂有哪些? #
32089次浏览 243人参与
# 校招阶段,学历VS技术哪个更重要? #
18986次浏览 197人参与
# 机械人春招想让哪家公司来捞你? #
349530次浏览 3088人参与
# 除了主业以外,你还有哪些其他收入? #
13258次浏览 203人参与
# 工作丧失热情的瞬间 #
294374次浏览 2373人参与
# 你最满意的offer薪资是哪家公司? #
33203次浏览 177人参与