P12421

注意事项

这是一道交互题，注意刷新缓存区。

对于 C++ 语言，推荐使用 endl 换行以刷新缓存区。

题目大意

给出

n

个点的树，树上有一个关键点

s

，操作至多

n-1

次，每次选择一个点

u

，交互库每次可以选择将

s

向

u

移动一步（

s=u

则不移动）或给出

s

到

u

的距离，最后需求出点

s

当前的位置，有多测。

$\sum n\le10^5$ 。

解法

不妨称交互库的两种行为分别为“移动”或“回复”。

观察不难发现“移动”将会带来更少的信息，首先考虑如果交互库一直“移动”我们要如何应对。

不难发现我们只要每次指定相同的

u

，那么

n-1

次操作后一定有

s=u

。方便起见我们将题目中给出的树视为以

u

为根的有根树。

那么如果某次交互库选择“回复”，那么我们不可能再次操作

u

了，因为交互库可以再次选择“回复”，而我们没有收到任何新的信息，相当于浪费了一次操作。

于是一旦某次交互库选择“回复”，那么我们考虑在接下来的操作中只需维护

s

的深度

t

以及

s

可能处在的子树的根节点

v

，初始时有

v=u

，

t=d+1

。

接下来从

u

开始进行一次 dfs，维护出每个点的深度（记为

h_i

）以及每个点为根的子树中有多少深度为

d+1

的点（记为

w_i

）。（注意不需要维护每个点为根的子树中有多少深度为

t

的点，即

t

改变时无需重新 dfs）

经过以上预处理后即可重复以下过程直到返回答案：

若 $h_v=t$ ，则直接返回 $v$ 。
否则，枚举 $v$ $v$ 的每个 $w_p$ $w_{p}$ 非 $0$ $0$ 的子节点 $p$ $p$ 并检查 $s$ $s$ 是否在 $p$ $p$ 子树内。
- 若 $p$ 是最后一个被检查的子节点，直接将 $v$ 置为 $p$ 并返回第 $1$ 步。
- 否则不断对 $p$ 操作直到进行了 $t-h_v+1$ 次或交互库选择了“回复”，期间交互库一定选择了“移动”，此时将 $t$ 置为 $t-1$ 即可。
- 结束对 $p$ $p$ 的操作后，有以下几种情况：
  - 进行了 $t-h_v+1$ 次操作后交互库仍未选择“回复”：此时直接返回 $p$ 即可。
  - 在第 $t-h_v+1$ 次操作时交互库才选择“回复”：此时若 $d=0$ ，返回 $p$ ；否则 $d=1$ ，返回 $v$ 。
  - 交互库提前选择了“回复”：此时若 $d=t-h_v-1$ ，则将 $v$ 置为 $p$ 并返回第 $1$ 步；否则 $d=t-h_v+1$ ，则可以判定 $s$ 不在 $p$ 子树内，继续枚举下一个 $p$ 即可。

不难发现上述过程一定能正确求解出

s

当前的位置。

次数分析

不难发现上述做法在某些情况下次数可能达到

n

，比如当原树为以

u

为中心的至少有

3

个节点的菊花，并且

s\neq u

时，交互库可以不断选择“回复”直到只剩

2

个可能的节点

x

和

y

，并且我们尝试操作

x

，那么此时交互库再选择“移动”，我们就耗尽了

n-1

次操作的机会，而需要一次额外的操作才能求出

s

当前的位置。

不难发现当

u

为叶节点时，上述情况就不会发生。（分析见下）

那么接下来分析交互次数：

一开始操作点 $u$ 时，交互库每“移动”一次，至少有 $1$ 个节点被排除了。（除非当前可能的 $s$ 只剩 $u$ ，但是这种情况并不重要，因为反正最多也就 $n-1$ 次操作）
若交互库第一次“回复”时就只有一个可能的 $s$ ，那么此时我们显然不会再进行任何更多的操作，所以这种情况也是合标的。
否则如果上述条件均成立（ $u$ 为叶节点且交互库第一次“回复”时有多于一个可能的 $s$ ），那么第一次“回复”时至少排除了 $2$ 个点（ $u$ 和与 $u$ 相邻的唯一的点）
接下来每步操作几乎都至少排除了 $1$ 个点：交互库始终提前选择“回复”，那么这里每次“移动”都等价于是最开始操作点 $u$ 时的移动，而每次“回复”都能至少排除 $1$ 个节点，由于最后还剩 $1$ 个节点，所以这里至多就是 $n-2$ 次操作（第一次“回复”时多排除了 $1$ 个点）。
否则一旦出现进行第 $t-h_v+1$ 次操作的情况就会立刻求解出答案，所以这里至多比上面多出 $1$ 步，也就是 $n-1$ 步。

综上，本做法完全满足本题的要求，且时空复杂度均容易做到

O(\sum n)

。

参考代码

这是我的赛时 AC 记录中的代码。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int T,I,n,m,u[110000],v[110000],num[110000],*mp[110000],deep[110000],siz[110000],fa[110000],d,i,j,op,x,o,pans,t;
void dfs(int x)
{
	int i;
	deep[x]=deep[fa[x]]+1;
	for(i=1;i<=mp[x][0];i++)
	if(mp[x][i]!=fa[x])
	{
		fa[mp[x][i]]=x;
		dfs(mp[x][i]);
		siz[x]=siz[x]+siz[mp[x][i]];
	}
	if(deep[x]==d)
	siz[x]++;
}
main()
{
	cin>>T;
	for(I=1;I<=T;I++)
	{
		cin>>n>>m;
		for(i=1;i<n;i++)
		cin>>u[i]>>v[i];
		for(i=1;i<n;i++)
		{
			num[u[i]]++;
			num[v[i]]++;
		}
		for(i=1;i<=n;i++)
		{
			mp[i]=new int[num[i]+1];
			mp[i][0]=0;
		}
		for(i=1;i<n;i++)
		{
			mp[u[i]][0]++;
			mp[u[i]][mp[u[i]][0]]=v[i];
			mp[v[i]][0]++;
			mp[v[i]][mp[v[i]][0]]=u[i];
		}
		for(i=1;i<=n;i++)
		if(num[i]<=1)
		break;
		o=i;
		for(i=1;i<=n-1;i++)
		{
			cout<<"? "<<o<<endl;
			cin>>op;
			if(op==2)
			{
				cin>>x;
				break;
			}
		}
		if(i>n-1)
		{
			cout<<"! "<<o<<endl;
			cin>>x;
			for(i=1;i<=n;i++)
			{
				num[i]=0;
				delete [] mp[i];
			}
			continue;
		}
		d=x+1;
		fa[o]=0;
		dfs(o);
		pans=siz[o];
		while(1)
		{
			if(deep[o]==d)
			{
				cout<<"! "<<o<<endl;
				cin>>x;
				break;
			}
			for(i=1;i<=mp[o][0];i++)
			if(mp[o][i]!=fa[o]&&siz[mp[o][i]]>0)
			if(siz[mp[o][i]]==pans)
			{
				o=mp[o][i];
				break;
			}
			else
			{
				t=d-deep[o]+1;
				for(j=1;j<=t;j++)
				{
					cout<<"? "<<mp[o][i]<<endl;
					cin>>op;
					if(op==1)
					d--;
					else
					{
						cin>>x;
						if(x==d-deep[mp[o][i]])
						{
							pans=siz[mp[o][i]];
							o=mp[o][i];
							op=3;
							break;
						}
						if(j==t)
						{
							if(x==0)
							cout<<"! "<<mp[o][i]<<endl;
							else
							cout<<"! "<<o<<endl;
							cin>>x;
							op=4;
							break;
						}
						break;
					}
				}
				if(op>2)
				break;
				if(j>t)
				{
					cout<<"! "<<mp[o][i]<<endl;
					cin>>x;
					op=4;
					break;
				}
				pans=pans-siz[mp[o][i]];
			}
			if(op==4)
			break;
		}
		for(i=1;i<=n;i++)
		{
			siz[i]=0;
			num[i]=0;
			delete [] mp[i];
		}
	}
}

碎碎念

怎么和官方题解做法完全不一样？

别忘了刷新缓存区，多测别忘清，别忘记读入每组数据给出答案后的 1。

~~赛时调了好久最后发现是 lca 挂了，一怒之下把 lca 删了，发现做法还是对的。（猜猜我一开始哪里用了 lca）~~

文章操作