[TIOJ] 1292. H.佔邊砍樹

題目連結:http://tioj.infor.org/problems/1292

---

裸樹上最小點覆蓋。而樹上最小點覆蓋該如何做呢?，不妨考慮先DFS一遍取得整棵樹的構造，之後從葉子走上去(可直接用DFS序列倒著跑)，若自己及自己的爸爸都沒有被任何點覆蓋，則把自己的爸爸放到點覆蓋集，因為這樣可以保證把所有點都放進去，而且因為是放爸爸進去，所以可以拿到最小的點覆蓋集。

#include <bits/stdc++.h>
using namespace std;

#define N 10000

vector<int> tree[N+10];
int deep[N+10];
vector<int> arr;
bitset<N+10> poped;

void DFS(int,int,int);

int n;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int s,e;
		scanf("%d%d",&s,&e);
		tree[s].push_back(e);
		tree[e].push_back(s);
	}
	int cnt=0;
	DFS(1,-1,0);
	for(int i=arr.size()-1;i>0;i--){
		int cc=arr[i];
		int ff=arr[i-1];
		if(deep[ff]>=deep[cc])continue;
		if(!poped[ff]&&!poped[cc]){
			poped[ff]=1;
			poped[cc]=1;
			cnt++;
		}
	}
	printf("%d",cnt);
	return 0;
}

void DFS(int w,int f,int d){
	deep[w]=d;
	for(auto i : tree[w]){
		if(i==f)continue;
		arr.push_back(w);
		DFS(i,w,d+1);
	}
	if(tree[w].size()==1&&f!=-1) arr.push_back(w);
}