题目链接：

题意：

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

 

分析：

对于每个节点，都有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 
      
       using namespace std;#define maxn 10005#define INF 0x3f3f3f3fint n;vector
       
         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
        
         =0;i--) {            int u = vertices[i];            d[u][0] = 1;            d[u][1] = 0;            for(int j=0;j
         
          INF) d[u][0] = INF;                if(d[u][1]>INF) d[u][1] = INF;            }            d[u][2] = INF;            for(int j=0;j