CF1695D2 Tree Queries (Hard Version) 做题记录

给定一棵无根树，有 $n$ 个顶点。在这棵树上有一个顶点 $x$，你希望找到它。

要找到 $x$，你可以进行 $k$ 次查询 $v_1 , v_2 ，\ldots , v_k$ (其中 $v_i$ 是树中的各个顶点)。当你进行完所有查询后，你会得到 $k$ 个数字 $d_1 , d_2 ，\ldots , d_k$ ，($d_i$ 是 $v_i$ 和 $x$ 之间的最短路径上的边数)。注意，您知道哪个距离对应于哪个查询。

请你求出最小的 $k$ ，使存在这样的一些查询 $v_1 , v_2 ，\ldots , v_k$ ，让你总能找到唯一的一个节点 $x$ (无论 $x$ 是什么)。

注意，你不需要输出这些查询。

$1 \le n \le 2\times 10^5$。

首先特掉 $n=1$ 和链的情况。

不难发现查询所有度为 $1$ 的叶子节点一定是可以的。

具体证明：

可以考虑从这些节点开始染色，遇到度数 $\ge 3$ 的点停下（度数 $\ge 3$ 的点不染色）。

那么若神秘点染了色那么一定能找到，否则删掉所有染了色的点后还是相当于询问了所有叶子节点，重复上述过程即可得证。

考虑从每个叶子节点 $u$ 开始染色停下的节点 $to_u$，设 $S_x=\{u|to_u=x\}$，那么答案即为 $\sum \max(|S_x|-1,0)$。

证明如下：

柿子的本质就是每个 $S_x$ 里可以少选一个，假设最后选的集合为 $A$，那么考虑所有满足 $u\in A,v\in A,u\not=v$ 的 $u,v$，那么 $u,v$ 之间的路径上的点都可以找到，把这些点染色。

考虑最后没被染色的点，显然它们构成了若干条链，每条链都一端“挂在”某两个被选择的点的路径上，所以也可以确定。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=500005;

int n;
int esum,to[S],nxt[S],h[S];
int d[S];
int tot,siz[S];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

int dfs(int u,int fa)
{
	int res=0;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		res+=dfs(v,u);
	}
	if(d[u]>=3)
	{
		tot+=res>0;
		return 0;
	}
	if(d[u]==1) return 1;
	return res;
}

inline void slove()
{
	scanf("%d",&n);
	esum=0;
	for(int i=1;i<=n;i++) h[i]=d[i]=0;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		d[x]++,d[y]++;
	}
	if(n==1)
	{
		puts("0");
		return;
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans+=d[i]==1;
	bool f=false;
	for(int i=1;i<=n;i++)
	{
		if(d[i]>=3)
		{
			f=true;
			tot=0;
			dfs(i,0);
			break;
		}
	}
	if(!f)
	{
		puts("1");
		return;
	}
	ans-=tot;
	printf("%d\n",ans);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}