【codeforces Round＃801 Div2 D题 Tree Queries】树形贪心结论

题目链接

题意：

给你一棵树，你需要执行多次询问来确定一个节点x的位置，对于每一次询问，你需要选择一个节点，能得到这个节点与x节点的距离是多少，问至少需要多少次询问才能确定x的位置。

分析：

有一个结论，就是选所有叶节点一定能表示出所有的节点，现在咱们来证明一下。选所有叶节点的话，叶节点的直接父节点就能唯一确定，那么咱们就把这些直接父节点作为新的叶节点来再唯一确定父节点的父节点，那么就能唯一确定所有的节点了，那么很显然选叶子节点是一定比选父节点优的，因为叶节点只有一个分支，不确定性更小，所以说如果最优解中有非叶子节点的话咱们可以替换成叶子节点而不影响最优性的，采用了交换论证的思想。当然咱们不能选所有的叶子节点，因为多余了，做法就是当遇到分叉的时候，这个分叉下面的叶子节点只删一个，这样子就能保证所有的节点都能唯一确定了。下面请看代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200010,M = N+N;
int n,cnt;
int du[N],h[N],e[M],ne[M],idx;
void add(int a,int b){
    
	du[a]++;
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
bool st[N];
void dfs(int u,int fa){
    
	for(int i=h[u];i!=-1;i=ne[i]){
    
		int j = e[i];
		if(j == fa) continue;
		if(!st[j] && du[j] > 2){
    
			cnt++;
			st[j] = true;
			return;
		}
		else if(st[j] && du[j] > 2) return;
		else dfs(j,u);
	}
}
void solve(){
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++) h[i] = -1,st[i] = false,du[i] = 0; 
	idx=0;cnt=0;
	int ans = 0;
	for(int i=1;i<n;i++){
    
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	} 
	int t1 = 0;
	for(int i=1;i<=n;i++){
    
		if(du[i] == 1) dfs(i,0),ans++;
		else if(du[i] == 2) t1++;
	}
	if(ans + t1 == n) printf("1\n");
	else
	printf("%d\n",ans-cnt);
}
int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		solve();
	}
	return 0;
}