不太重要的思考

注意到一个奇奇怪怪的计分公式，然而我们应当追求满分，于是这题的要求就变成了询问次数不得超过 9 次。

套路的思考

看到数据范围里点数不超过 500，这恰好略小于

2^9=512

，那么通常的套路就是每次排除至少向下取整一半的答案，也就是二分法。这样一来，不超过 9 次就可以确定最后的答案。

做法的思考

题目保证了一个性质，就是树上至少有一个点度数大于 2，暂时不知道是干什么用的，只知道树不会退化成一条链。

考虑询问，可以发现如果我们询问的点包含了树根的话，返回的一定是 YES。问题就在于，如果我们询问的点不包含树根的话，会返回什么？根据题意，返回的是询问点的最近公共祖先是否在询问点中。结果返回的是 YES 或 NO 都有可能。

反过来想，能否令返回 YES 的时候，树根一定在询问点中；返回 NO 的时候，树根一定不在询问点中？

有根树有一个性质，在很多有关最近公共祖先的题目中都或多或少有所体现：若干个点的最近公共祖先要么在询问点之中，要么是询问点的公共祖先，且询问点分跨多个子树（“多个”指大于一个）。

于是我们能够反着利用这个性质，确保询问点分跨它们的最近公共祖先的多个子树（返回 NO），或者询问点的最近公共祖先就在询问点之中（返回 YES），就可以保证询问所返回的 YES 或 NO 代表了询问点的最近公共祖先是否在询问点之中了。

接下来就是令询问点的最近公共祖先是树根了。容易发现，所有叶子结点一定分跨树根的多个子树，或者树根就是叶子结点之一。于是我们确保询问时尽可能带上所有叶子结点。

实现

具体实现的时候，询问答案候选区间中的点中的一半节点，以及不在答案候选区间中的叶子结点。不在答案候选区间的叶子结点有助于保持询问返回 NO 时询问点分跨树根的多个子树。

为什么说有助于，而不是确保呢？在二分的时候，答案候选区间的一半点被询问，另一半不被询问。这导致一个风险：叶子结点过多出现在不被询问的半边答案候选区间。在不被询问的半边答案候选区间是叶子结点不被询问的唯一可能。为了解决这个问题，假设询问答案候选区间的前一半，则将叶子结点放在所有其他节点前面即可。实现时将节点按度数从小到大排序也可以通过，时间非常宽松。如果你喜欢询问后一半，则将叶子结点后置，或者度数从大到小排序。

对于这么做的正确性，简单地证明一下：

证明

我们知道答案候选区间的点的最近公共祖先一定是树根，因为树根就在答案候选区间中。考虑在节点没有排序时唯一会产生误判的情况（会在询问点不包含树根时返回 YES），即答案候选区间的前一半的点的最近公共祖先不是树根，且属于答案候选区间的前一半的点的情况。

答案候选区间的前一半的点都是叶子结点：因为这些节点的最近公共祖先属于这些节点，而叶子结点作为多个点的最近公共祖先的唯一可能就是这个叶子结点就是树根，和前提“答案候选区间的前一半的点的最近公共祖先不是树根”矛盾；
答案候选区间的前一半有部分是叶子结点，或没有叶子结点：这意味着答案候选区间的后一半没有叶子结点，因为叶子结点在非叶子结点前。这样的话，询问点会包含所有叶子结点，性质良好，不会误判。

证明时提到了“多个点”，不禁担忧：如果询问的点只有一个点，有没有问题？当实现二分时询问区间为答案候选区间的前至少一半，也就是长度为答案候选区间长度的向上取整一半时，询问点仅有一个点当且仅当答案候选区间长度为二。这时，最开头提到的性质，即树不是一条链，就派上了用场：这棵树至少有三个叶子结点！也就是说，至少有一个叶子结点不在答案候选区间里了，询问点仍然包含多个叶子结点。

其他情况：

答案候选区间的前一半的点的最近公共祖先是树根：这时性质良好，要么树根属于答案候选区间的前一半，要么这些点跨过了树根的多个子树；
答案候选区间的前一半的点的最近公共祖先不是树根，且不属于答案候选区间的前一半的点：这时性质也良好，会返回 NO。

证毕。

虽然啰里吧嗦地证明了一大串，但实现起来相当方便，想出结论也远比证明轻松。看代码吧：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,du[502],p[502];
bool cmp(ll a,ll b)
{
	return du[a]<du[b];
}
string s;
int main()
{
	cin>>n;
	for(ll i=1;i<n;i++)
	{
		ll u,v;
		cin>>u>>v;
		du[u]++;
		du[v]++;
	}
	for(ll i=1;i<=n;i++)p[i]=i;
	sort(p+1,p+n+1,cmp);
	ll l=1,r=n;
	while(l<r)
	{
		ll mid=(l+r)>>1;
		cout<<"?";
		ll cnt=0;
		for(ll i=1;i<=n;i++)
		{
			if(l<=i&&i<=mid||(i<l||i>r)&&du[p[i]]==1)cnt++;
		}
		cout<<' '<<cnt;
		for(ll i=1;i<=n;i++)
		{
			if(l<=i&&i<=mid||(i<l||i>r)&&du[p[i]]==1)cout<<' '<<p[i];
		}
		cout<<endl;
		cin>>s;
		if(s=="NO")l=mid+1;
		else r=mid;
	}
	cout<<"! "<<p[l]<<endl;
	return 0;
}

题解：P13782 [eJOI 2022] Where Is the Root?

文章操作

不太重要的思考

套路的思考

做法的思考

实现

相关推荐

评论

题解：P13782 [eJOI 2022] Where Is the Root?