自动搬运

查看原文

来自洛谷，原作者为

	XGTD XGTD 星光铁蛋，不在星光了，但还是星光铁蛋

搬运于2025-08-24 23:10:41，当前版本为作者最后更新于2025-03-05 10:09:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P11840 [USACO25FEB] Vocabulary Quiz S

不是，现在银组都简单成这样了？看看去年二月银组，难度可是直逼铂金呀。

视频题解。

介绍一种时间复杂度 $O(n)$，非常简单直白，码量小，且不需要 st 表，lca 的方法。

Problem Statement

P11840。

Solution

虽然题目感觉有些绕，但是很快就能发现其实这 $n - 1$ 个点构成的就是一颗以节点 0 为根的树，每个节点的父节点就是 $p_i$，而那 $m$ 个 "不作为另一个单词前缀的单词" 就是所有的叶子节点。

现在我们先不考虑读的顺序，就是假设目前还没有任何单词因为被读过而删除掉了。

我们发现对于一个叶节点 $i$，想要知道它的具体身份至少需要读到的字符数就是 $i$ 深度最深的，有超过一个儿子的祖先节点的深度。为什么呢？设这个节点是 $j$, 发现如果我们不把 $j$ 读完，我们并不知道这个单词到底是 $i$，还是 $j$ 的另一个儿子下的某一个叶子，因此至少需要把 $j$ 读完，且还要再多读一个字符。同时读 $dep_j + 1$ 也一定足够确定 $i$ 了（$dep_j$ 为 $j$ 节点的深度），因为我们知道从 $j$ 到 $i$ 没有任何其他节点有超过一个儿子了，因此 $j$ 下面唯一的叶节点就是 $i$。

现在发现删除节点也很简单了，直接将此节点的父亲出度减一就行了。如果发现一个节点的出度已经为零了（儿子被删完了）说明他下面没有叶节点了，就把它也删除就行了。

代码十分简洁好写。

Code

赛时代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, p[1000005], dep[1000005];
int cnt[1000005];
vector<int> e[1000005];
void pdfs(int x){
	dep[x] = dep[p[x]] + 1;
	if(!cnt[x])m++;
	for(auto i: e[x]){
		pdfs(i);
	}
}
int rdfs(int x){
	if(cnt[x]){
		//this point has other sons
		return dep[x] + 1;
	}
	if(x == 0){
		//last one
		return 0;
	}
	cnt[p[x]]--;//erase this node
	return rdfs(p[x]);
}
signed main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>p[i];
		cnt[p[i]]++;
		e[p[i]].push_back(i);
	}
	p[0] = 0;
	dep[0] = -1;
	//so when we do dep[i] = dep[p[i]] + 1 we have dep[0] = 0
	pdfs(0);
	//pre process depth and m
	for(int i = 1; i <= m; i++){
		int now;
		cin>>now;
		cout<<rdfs(now)<<endl;
		//reverse dfs
	}
	return 0;
}

After thoughts

对于银组来说真的太简单了，顺着想一步一步非常直白就出来了，考场上花了大概 10 分钟。