题目链接：http://poj.org/problem?id=3659
题目描述：
给你一棵无向树，问你最少选多少个点，可以使选中的点和剩余的所有其他的点都有边相连。
（一个点被选中，它自己和与它相邻的点都算有边相连）
解题报告：
一.贪心（ O(n) ）
贪心，随便找一个根，前序遍历树。
然后从叶子开始遍历，对于当前还未被访问的结点，如果其父亲还未被选中，就将其父亲结点选中，答案加一，并标记其自身和父亲已访问。
AC代码：
1 #include<vector> 2 #include<cstdio> 3 #include<iostream> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #define numm ch-48 8 #define pd putchar(' ') 9 #define pn putchar(' ') 10 #define pb push_back 11 #define fi first 12 #define se second 13 #define fre1 freopen("1.txt","r",stdin) 14 #define fre2 freopen("2.txt","w",stdout) 15 using namespace std; 16 template <typename T> 17 void read(T &res) { 18 bool flag=false;char ch; 19 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 20 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 21 flag&&(res=-res); 22 } 23 template <typename T> 24 void write(T x) { 25 if(x<0) putchar('-'),x=-x; 26 if(x>9) write(x/10); 27 putchar(x%10+'0'); 28 } 29 const int maxn=10010; 30 const int N=1010; 31 const int inf=0x3f3f3f3f; 32 typedef long long ll; 33 struct node { 34 int v,net; 35 }e[maxn<<1]; 36 bool vis[maxn],choose[maxn]; 37 int p[maxn],now,cnt,n,newpos[maxn],head[maxn]; 38 void add(int u,int v) { 39 e[++cnt].v=v; 40 e[cnt].net=head[u]; 41 head[u]=cnt; 42 } 43 void dfs(int x) { 44 newpos[++now]=x; 45 for(int k=head[x];k!=-1;k=e[k].net) { 46 int to=e[k].v; 47 if(!vis[to]) { 48 vis[to]=true; 49 p[to]=x; 50 dfs(to); 51 } 52 } 53 return ; 54 } 55 int greedy() { 56 for(int i=1;i<=n;i++) 57 vis[i]=false; 58 int ans=0; 59 for(int i=n;i>=1;i--) { 60 int t=newpos[i]; 61 if(!vis[t]) { 62 if(!choose[p[t]]) { 63 choose[p[t]]=true; 64 ans++; 65 } 66 vis[t]=true; 67 vis[p[t]]=true; 68 vis[p[p[t]]]=true; 69 } 70 } 71 return ans; 72 } 73 int main() 74 { 75 read(n); 76 for(int i=1;i<=n;i++) 77 head[i]=-1; 78 for(int i=1;i<=n-1;i++) { 79 int a,b; 80 read(a),read(b); 81 add(a,b); 82 add(b,a); 83 } 84 vis[1]=true; 85 dfs(1); 86 write(greedy());pn; 87 return 0; 88 }
二.树状动态规划（树形dp）（ O(n) ）
解法在此：https://www.cnblogs.com/wuliking/p/11264124.html，此处不再赘述。
AC代码：
1 #include<vector> 2 #include<cstdio> 3 #include<iostream> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #define numm ch-48 8 #define pd putchar(' ') 9 #define pn putchar(' ') 10 #define pb push_back 11 #define fi first 12 #define se second 13 #define fre1 freopen("1.txt","r",stdin) 14 #define fre2 freopen("2.txt","w",stdout) 15 using namespace std; 16 template <typename T> 17 void read(T &res) { 18 bool flag=false;char ch; 19 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 20 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 21 flag&&(res=-res); 22 } 23 template <typename T> 24 void write(T x) { 25 if(x<0) putchar('-'),x=-x; 26 if(x>9) write(x/10); 27 putchar(x%10+'0'); 28 } 29 const int maxn=10010; 30 const int N=1010; 31 const int inf=0x3f3f3f3f; 32 const int INF=0x7fffffff; 33 typedef long long ll; 34 struct node { 35 int v,net; 36 }e[maxn<<1]; 37 int cnt,n,head[maxn]; 38 int dp[maxn][3]; 39 void add(int u,int v) { 40 e[++cnt].v=v; 41 e[cnt].net=head[u]; 42 head[u]=cnt; 43 } 44 void DP(int u,int p) { ///u:当前结点，p：u的父结点 45 bool flag=false; ///标记是否有一个dp[to][0]<=dp[to][1] 46 int sum=0,inc=INF; 47 dp[u][2]=0; ///第三状态，当前结点未被选中 48 dp[u][0]=1; ///第一状态，当前结点被选中，dp[u][0]+1 49 for(int i=head[u];i!=-1;i=e[i].net) { 50 int to=e[i].v; 51 if(to==p) continue; ///to必须是u的子节点，不是父节点(由根dp到叶子) 52 DP(to,u); ///dp子节点 53 dp[u][0]+=min(dp[to][0],min(dp[to][1],dp[to][2])); ///回溯，第一状态的转移 54 if(dp[to][0]<=dp[to][1]) { ///第二状态的判断 55 flag=true; 56 sum+=dp[to][0]; 57 } 58 else { 59 sum+=dp[to][1]; 60 inc=min(inc,dp[to][0]-dp[to][1]); 61 } 62 if(dp[to][1]!=INF&&dp[u][2]!=INF) ///第三状态的转移 63 dp[u][2]+=dp[to][1]; 64 else dp[u][2]=INF; ///根据定义dp[u][2]=（dp[to][1]的总和） 65 } 66 if(!flag&&inc==INF) ///判断当前是不是叶子结点 67 dp[u][1]=INF; 68 else 69 dp[u][1]=sum+(flag?0:inc); 70 } 71 int main() 72 { 73 read(n); 74 for(int i=1;i<=n;i++) 75 head[i]=-1; 76 for(int i=1;i<=n-1;i++) { 77 int a,b; 78 read(a),read(b); 79 add(a,b); 80 add(b,a); 81 } 82 DP(1,1); 83 write(min(dp[1][0],dp[1][1]));pn; 84 return 0; 85 }