页面加载中…
P6100. 迷宫
中等通过率 100% · 提交 8 · 通过 8
DFS树二叉树枚举
华为 OD 机考真题方向改编 · 聚焦「DFS / 树」 · 难度：中等
小慕在梦中被困在了一座迷宫里。这座迷宫实在太复杂了，小慕发动了特殊能力，让迷宫变得简单起来。迷宫变成了一棵有n个节点的（根节点为1），只能从一个节点走向它的子节点，而当某个节点没有子节点时，就表示走到了。这样一来，小慕只要沿着任意可行的路径前进，就一定能找到出口！ 出发前，为了做好充分准备，小慕想知道在迷宫的每个位置分别能到达哪些出口。
这类题属于华为 OD 机考真题方向中「DFS / 树」方向的高频题型，通常考察对「DFS / 树」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行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个整数，分别表示每次询问的答案。
示例
示例 1
输入示例
3 2 3 1 1 2 3 1 2 3
输出示例
2 1 1
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
