洛谷 U658543 - 寻隐者不遇题解

Tiger

发表于 2026-02-26

更新于 2026-02-26

题解

11 1.5~1.9 分钟 653

题面

贾岛想要到山中求见隐者，却只看到了隐者的徒弟，也就是故事中的童子。童子也不知道隐者的位置，但他给出了如下线索：

山中有 $n$ 个采药点，这些采药点依次编号为 $1 \sim n$ 采完每个采药点的药后可以选择接下来的与该采药点相接的两个采药点中的一个，每次移动花费 1 个单位时间。保证除第 1 个采药点外，其余采药点只能由唯一的一个采药点直接到达。

童子告诉了贾岛从第 1 个采药点开始，每个采药点可以到达的两个采药点，并给出隐者从第 1 个采药点开始，已经采药了 $t$ 个单位时间，贾岛发现采药点的集合可以视作一颗完全二叉树，并希望根据这些信息缩小查找范围。请你帮助贾岛依据上述信息给出可能的隐者位置的编号。

分析

这是一道完全二叉树的题目，主要考察的是完全二叉树的构造和遍历。可以使用模板解决。除此之外，我们还将介绍一种做法：

对于每个节点，其子节点的层数都是其本身层数加 1，于是我们可以列出如下的式子：

depth_{left} = depth_{right} = depth_{node} + 1

其中 $left$ 表示左子结点， $right$ 表示右子节点， $node$ 表示父节点。

如此，我们初始化 $f[1] = 0$ ，然后根据这个式子，在输入时处理节点层数。由于题目保证节点自上而下进行输入，因此可以用这种方法解决。最后遍历一遍所有节点，找出节点层数为 $n$ 的节点，按编号升序输出即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {

    int n, t;
    cin >> n >> t;
    vector<int> left(n + 1), right(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> left[i] >> right[i];
    }

    vector<int> depth(n + 1, -1);
    queue<int> q;
    depth[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (left[u] != 0) {
            depth[left[u]] = depth[u] + 1;
            q.push(left[u]);
        }
        if (right[u] != 0) {
            depth[right[u]] = depth[u] + 1;
            q.push(right[u]);
        }
    }

    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        if (depth[i] == t) {
            ans.push_back(i);
        }
    }
    sort(ans.begin(), ans.end());

    for (int v : ans) {
        cout << v << endl;
    }

    return 0;
}