[codeworks round 801 div2 D tree queries] tree greedy conclusion

Topic link

The question ：

Give you a tree , You need to perform multiple queries to determine a node x The location of , For every inquiry , You need to select a node , You can get this node and x What is the distance between nodes , Ask at least how many times it takes to be sure x The location of .

analysis ：

There is a conclusion , That is, selecting all leaf nodes must represent all nodes , Now let's prove it . If all leaf nodes are selected , The direct parent node of the leaf node can be uniquely determined , Then let's take these direct parent nodes as new leaf nodes to uniquely determine the parent node of the parent node , Then we can uniquely determine all nodes , Then it is obvious that selecting leaf nodes is better than selecting parent nodes , Because the leaf node has only one branch , Less uncertainty , So if there are non leaf nodes in the optimal solution, we can replace them with leaf nodes without affecting the optimality , The idea of exchange argument is adopted . Of course, we can't choose all leaf nodes , Because it's redundant , The way to do it is when you encounter bifurcation , Only one leaf node under this bifurcation is deleted , This will ensure that all nodes can be uniquely identified . Now look at the code ：

#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;
}