题意：有以个 有 N 个节点的树形地图，问在这些顶点上最少建多少个电话杆，可以使得所有顶点被覆盖到，一个节点如果建立了电话杆，那么和它直接相连的顶点也会被覆盖到。

分析：用最少的点覆盖所有的点，即为求最少支配集。  可以用树形DP。

       ①  dp[r][0] += min(dp[i][0],dp[i][1],dp[i][2])    dp[r][0]表示在自 r 顶点自身建， 以 r 为根节点的树所需要的最少覆盖数。

       ②  dp[r][1] += min(dp[i][0],dp[i][1])                dp[r][1]表示在r 的子节点建，     以 r 为根节点的树所需要的最少覆盖数。

       ③  dp[r][2] += min(dp[i][0],dp[i][1])                dp[r][2]表示在r 的父节点建，     以 r 为根节点的数所需要的最少覆盖数。

   

 对于dp[i][1],要考虑全面，也就是说：必须要有一个孩子建塔，才能保证i被覆盖（Min=sum(min(dp[v][0]-dp[i][1]))，也就是当所有孩子的dp[v][0]>dp[v][i]时，Min表示他们差值最小的那个差值）。

    所以方程是dp[i][1]+=min(dp[v][0],dp[1])（至少存在一个孩子的dp[v][0]<=dp[v][1]，否则要dp[i][1]+=Min）；

AC代码：

#include
      
       #include
       
        #include
        
         #define M 10007#define inf 0x3f3f3fusing namespace std;int dp[M][3];int head[M],k,n;bool vis[M];struct sa{    int v,next;}edg[M*2];void addedge(int u,int v){    edg[k].v=v;    edg[k].next=head[u];    head[u]=k++;}void dfs(int key){    bool flag=true;    vis[key]=false;    dp[key][0]=1;    dp[key][1]=dp[key][2]=0;    int minn=inf;    for(int i=head[key];i!=-1;i=edg[i].next)    {        int v=edg[i].v;        if(vis[v])        {            dfs(v);            dp[key][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));            dp[key][2]+=min(dp[v][0],dp[v][1]);            if(dp[v][0]<=dp[v][1])            {                flag=false;                dp[key][1]+=dp[v][0];            }            else            {                dp[key][1]+=dp[v][1];                minn=min(minn,dp[v][0]-dp[v][1]);            }        }    }        if(flag)            dp[key][1]+=minn;}int main(){    //freopen("in.txt","r",stdin);    while(scanf("%d",&n)!=EOF)    {        memset(vis,true,sizeof(vis));        memset(head,-1,sizeof(head));        k=1;        int a,b;        while(--n)        {            scanf("%d%d",&a,&b);            addedge(a,b);            addedge(b,a);        }        dfs(1);        printf("%d\n",min(dp[1][0],dp[1][1]));    }    return 0;}