Uva 1218 完美的服务

题目链接：https://uva.onlinejudge.org/external/12/1218.pdf

题意：

一个网络，选出一些点做服务器，使满足一些条件，求服务器最少数量。条件是，每个计算机恰有一台服务器相连。

分析：

对于每个节点，都有3种状态，1、他是服务器 d(u,0)，2、他不是服务器，但是父亲是的 d(u,1)，如果他父亲是服务器，将影响他的接下来的决策。3、他不是服务器，父亲也不是服务器 d(u,2);

那么： 

d(u,0) = sum{max{d(v,0),d(v,1)}};

d(u,1) = sum{d(v,2)};

d(u,2) 子节点恰有一台是服务器，可以利用 上面的求出， d(u,2) = min{d(u,1)-d(v,2)+d(v,0)};

建树时，可以以任一点为根。

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

#define maxn 10005
#define INF 0x3f3f3f3f

int n;
vector<int> G[maxn],vertices;
int p[maxn],d[maxn][3];

//建树
void dfs(int u,int fa) {
    vertices.push_back(u);
    p[u] = fa;
    for(int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if(v!=fa)
            dfs(v,u);
    }
}


int main()
{
    while(scanf("%d",&n),n!=-1) {

        for(int i=0;i<n;i++)
            G[i].clear();

        for(int i = 0;i<n-1;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            u--;
            v--;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        vertices.clear();
        dfs(0,-1);
        memset(d,0,sizeof(d));

        for(int i=vertices.size()-1;i>=0;i--) {
            int u = vertices[i];
            d[u][0] = 1;
            d[u][1] = 0;
            for(int j=0;j<G[u].size();j++) {
                int v = G[u][j];
                if(v==p[u]) continue;
                d[u][0] +=min(d[v][0],d[v][1]);
                d[u][1] +=d[v][2];
                if(d[u][0]>INF) d[u][0] = INF;
                if(d[u][1]>INF) d[u][1] = INF;
            }
            d[u][2] = INF;

            for(int j=0;j<G[u].size();j++) {
                int v = G[u][j];
                if(v==p[u]) continue;
                d[u][2] = min(d[u][2],d[u][1]-d[v][2]+d[v][0]);
            }

        }
        printf("%d
",min(d[0][0],d[0][2]));
        scanf("%d",&n);

    }
    return 0;
}