题解：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

赛时代码。

CPP

#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 分钟。

题解：P11840 [USACO25FEB] Vocabulary Quiz S

文章操作

题解：P11840 [USACO25FEB] Vocabulary Quiz S

Problem Statement

Solution

Code

After thoughts

相关推荐

评论

题解：P11840 [USACO25FEB] Vocabulary Quiz S