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、如果遍历次数等于特殊节点数量,即为符合要求的节点