UVA 1292-Strategic game（树形DP）

题目大意：给出一棵树，在某个选择某个结点可以覆盖和它相连的所有边，问最少选多少个结点所有边都被覆盖。

首先将无根树转化为有根树，0为根。

用d[i][0]表示不选择结点i时覆盖以结点i为根的子树最少要多少个结点，用d[i][1]表示选择结点i时覆盖以结点i为根的子树最少要多少个结点。若结点i不选，为了和覆盖所有和结点i相连的结点，则每个儿子都必须选，若结点i选，则每个儿子选择较小的那个值。按DFS顺序递推。

状态转移方程：

d[i][0]=sum { d[u][1] }（u是i的儿子）

d[i][1]=sum { min { d[u][0],d[u][1] } }+1（u是i的儿子）

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int a[30]; int d[1510][2]; char e[1510]; int par[1510]; vector
      
        G[1510]; void dfs(int u); void rootedtree(int u,int fa); int main(void) { int i,j,u,n,sump,top,lo; while(scanf("%d",&n)==1) { for(i=0;i
       
        ='0')&&(e[j]<='9')) { sump=0; while((e[j]>='0')&&(e[j]<='9')) { sump=sump*10+e[j]-'0'; j++; } top++; a[top]=sump; } else { j++; } } for(j=1;j<=a[2];j++) { scanf("%d",&u); G[a[1]].push_back(u); G[u].push_back(a[1]); } } rootedtree(0,-1); for(i=0;i
        
         d[0][1]?d[0][1]:d[0][0]); } return 0; } void dfs(int u) { int i,p,minp,sump; p=G[u].size(); if(p==0) { d[u][0]=0; d[u][1]=1; } else { for(i=0;i
         
          d[G[u][i]][1]?d[G[u][i]][1]:d[G[u][i]][0]); sump=sump+d[G[u][i]][1]; } d[u][0]=sump; d[u][1]=minp+1; } } void rootedtree(int u,int fa) { int i,v,p; p=G[u].size(); for(i=0;i