Vocabulary Quiz (USACO Silver 2025 February)

理解一下题意，应该就可以发现，词之间的关系组成一棵以0为根的树，所有的叶子节点都在词库中的词。而每次报一个词，就是要找到最大（离根最近）的子树，只包含这一个叶子节点，然后输出这个子树的根离根节点的距离。报完之后，删除这个叶子节点。

如果用模拟的办法来解这个题，会发现复杂度是 $\mathcal{O}(N^2)$ 的。可以用倍增这样的办法来解决，但写起来比较繁琐。

正解是不使用模拟，而是考虑以下性质：记录每个叶子节点读出的时间 $t[i]$ ，所有其中最大叶子节点时间是 $t[i]$ 的子树中离根最近的那棵的深度，就是这个叶子节点对应的单词需要朗读的字节数量。每个子树中叶子节点最大的 $t[i]$ 的意思，就是我们在做模拟时，子树中所有其它其它叶子节点到 $t[i]$ 时都已经被删除了，所以子树的最小深度，就是我们要求的答案。

通过DFS，可以一遍扫描计算出每个子树中最大的 $t[i]$ ，对每个 $t[i]$ 求出所有对应子树的最小深度，就是答案了。 $\mathcal{O}(N)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=1000010;
int n,m,a[N],t[N],p[N],ans[N];
// a,t记录朗读顺序，p[i]表示以i为根的子树最晚读出字符串是哪个，ans表示答案
vector<int> v[N];  // 邻接表
 
void dfs(int x, int d) {
    p[x] = x;
    for (int y: v[x]) {
        dfs(y, d+1);
        if (t[p[y]] > t[p[x]]) 
            p[x] = p[y];        // 求出子树内最晚被读出的叶子
    }
    ans[t[p[x]]] = d;           // 更新读叶子的答案
    // 注意DFS顺序，较小的深度会更晚更新，所以这里可以直接等于
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        v[x].push_back(i);      // 建树
    }
    for (int i = 1; i <= n; i++) {
        if (!v[i].size()) m++;  // 求出有多少叶子
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
        t[a[i]] = i;            // 记录每个叶子的读出顺序
    }
    dfs(0, 0);
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}