【Link】:

【Description】



给你n个机器组成的一棵树,然后,让你在某些机器上安装服务器.

要求,每个机器如果没有安装服务器,都要恰好和一个安装了服务器的机器连接.

问你,最少要安装多少个服务器

【Solution】



比较常见的树形DP

f[i][0]表示,i这个节点没装服务器,然后i这个节点没被儿子节点中的某一个控制,且儿子节点都已经符合要求的的最小服务器数.

f[i][1]表示,i这个节点没装服务器,然后i这个节点被儿子节点中的某一个控制,且i以下的节点都已经符合要求的最小服务器个数.

h[i]表示,i这个节点装了服务器,且以下的节点都已经符合要求的最小服务器个数.

转移的时候

(以下,j都为i的儿子节点)

f[i][0]=∑f[j][1]

h[i]=∑max(h[j],f[j][0])

f[i][1]=∑f[j][1]+h[idx]−f[idx][1]

这里的idx是i的儿子节点中h的值最小的那个;

表示要选一个儿子节点装上服务器,来控制这个i节点.

对于叶子节点cnt

f[cnt][0]=0,f[cnt][1] = INF,h[cnt] = 1;

这里如果某个时刻,∑f[j][1] >= INF,则说明i节点会是倒数第二层的节点;

则可以在最底层中的某一个装服务器,则直接把f[i][1]赋值为h[idx][1]就好;

左边的∑符号里的东西可以省去了。

加的时候可能会超int,所以大于INF了就变成INF



【NumberOf WA】



1



【Reviw】



这道题的数据挺水的。。



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 10000;

const int INF = 0x3f3f3f3f;

int n,f[N+100][2],h[N+100];

vector <int> g[N+100];

void limit(int &x){

    x = min(x,INF);

}

void dfs(int x,int fa){

    if (x!=1 && (int) g[x].size() == 1){

        f[x][0] = 0;

        f[x][1] = INF;

        h[x] = 1;

        return;

    }

    //f[i][0],没放服务器,没被控制,最小服务器个数

    //f[i][1],没放服务器,被控制了,最小服务器个数

    //h[i],放了服务器,且下面都被合法控制,最小服务器个数

    f[x][0] = f[x][1] = 0;

    h[x] = 1;

    int len = (int) g[x].size();

    int mi = INF,idx = 0;

    rep1(i,0,len-1){

        int y = g[x][i];

        if (y==fa) continue;

        dfs(y,x);

        if (h[y] < mi){

            mi = h[y];

            idx = y;

        }

        f[x][0] += f[y][1];

        limit(f[x][0]);

        f[x][1] += f[y][1];

        limit(f[x][1]);

        h[x] += min(f[y][0],h[y]);

        limit(h[x]);

    }

    if (f[x][1]>=INF){

        f[x][1] = h[idx];

    }else{

        f[x][1] -= f[idx][1];

        f[x][1] += h[idx];

    }

    limit(f[x][1]);

}

int main(){

    //Open();

    //Close();

    int t = 0;

    while (t==0){

        rep1(i,1,N) g[i].clear();

        scanf("%d",&n);

        rep1(i,1,n-1){

            int x,y;

            scanf("%d%d",&x,&y);

            g[x].pb(y),g[y].pb(x);

        }

        dfs(1,0);

        printf("%d\n",min(h[1],f[1][1]));

        scanf("%d",&t);

        if (t==-1) break;

    }

    return 0;

}