树(tree)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小王喜欢数据结构,尤其是唱歌。
小王有一棵 个点的树,点从 到 编号,根是 ,点 的父亲是 。每个点的 儿子按编号从小到大排序。每个有儿子的点有一个指针,初始指向第一个儿子。
接下来小王进行 次巡演,每次他从根出发,然后不停沿着所在点的指针走向一 个儿子,直到到达一个叶子。每走过一个点,这个点的指针就改为指向下一个儿子,如 果这已经是最后一个儿子则指向第一个儿子。
请你求出小王的每次巡演结束于哪个叶子。
输入格式
第一行包含两个正整数 , 分别表示树的点数和巡演的次数。
第二行包含 个正整数 。
输出格式
行,第 行一个数,表示第 次巡演结束的叶子的编号。
样例输入输出
10 10
1 2 2 1 2 4 3 2 8
5
4
7
10
5
9
7
4
5
10
样例 2
见附件下的 tree/tree2.in 与 tree/tree2.ans。
说明/提示
【样例 #1 解释】
树的形态如图所示:
初始每个有儿子的点的指针为: 指向 , 指向 , 指向 , 指向 , 指向 。
第 次巡演,小王依次经过点 ,这使得 的指针指向 , 的指针指向 ,其它点的指针不变。
第 次巡演,小王依次经过点 ,这使得 的指针指向 ,其它点的指针不变。
第 次巡演,小王依次经过点 ,这使得 的指针指向 , 的指针指向 , 其它点的指针不变。
【数据范围及约束】
对于所有数据,保证 。
测试点编号 | 特殊性质 | |
---|---|---|
在 中等概率随机生成 | ||
【题目来源】
2023 青岛市程序设计竞赛 高中组 T1 tree