题目描述
杭州市的中心广场有一棵著名的古树。这棵古树可以看作一棵
称没有孩子的节点为叶子节点。古树每次落叶时,会选择一个当前的叶子节点删去。每一天中,古树可能会多次落叶。
有
每一天,收集所有新的落叶的编号(即当天删除的节点的编号),然后将它们按任意顺序写在先前的落叶编号之后。
例如:第一天,叶子
这个过程持续了
你在旅途过程中经过了杭州。此刻已是寒冬,仰望古树光秃秃的枝干,你不禁想起落叶纷飞的美丽景象。
你很想知道今年有几天能看见落叶,但你只能找到
实现细节
请在程序开头引入库 september.h
。
你需要实现以下函数:
int solve(int N, int M, std::vector<int> F,
std::vector<std::vector<int>> S);
:古树的节点数量。 :志愿者的数量。 :一个长度为 的数组。对于 , 表示节点 的父亲节点的编号。 始终为 。 :一个长度为 的数组。 中的每个元素是一个长度为 的数组。 表示志愿者 记录的第 个节点编号(从 开始)。
该函数必须返回一个整数,表示根据如上规则的
对于每个测试点,交互库可能调用该函数多于一次。每次调用都应该作为新的情况分别处理。
注意:由于函数调用可能会发生多次,选手需要注意之前调用的残余数据对于后续调用的影响,尤其是全局变量的状态。
样例 1
考虑如下调用:
solve(3, 1, {-1, 0, 0}, {{1, 2}});
对应的树如下图所示:
叶子
因此,程序应当返回
样例 2
考虑如下调用:
solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});
对应的树如下图所示:
假设至少有
因此,程序应当返回
约束条件
。 。 。 。对于 , 。- 对于
,数组 是一个 的排列。 - 保证
描述的是一棵以节点 为根的有根树。
子任务
详细子任务附加限制及分值如下表所示。
子任务编号 | 附加限制 | 分值 |
---|---|---|
1 | 11 | |
2 | 14 | |
3 | 5 | |
4 | 9 | |
5 | 5 | |
6 | 11 | |
7 | 9 | |
8 | 11 | |
9 | 9 | |
10 | 没有额外的约束条件 | 16 |
评测程序示例
评测程序示例读取如下格式的输入:
- 第
行:
对于接下来的
- 第
行: - 第
行: - 第
( ) 行:
评测程序示例按照如下格式打印你的答案:
对于每组测试数据:
- 第
行:函数solve
的返回值