题解：UVA1218 完美的服务 Perfect Service

liyancen · 2025-02-11 17:12:04 · 题解

考虑树形dp，不难想到我们会用到三个状态，具体如下

那么我们就不难想到会有以下几个状态转移方程：

注：v_i 表示 x 的孩子。

上面的两个状态转移方程非常好想对吧，按照dp的定义即可推导出来，关键就是在于 dp[x][2]。

题目中要求了，只能有一个服务器与之相连，所以说我们很容易想出用暴力的思想，暴力枚举所有儿子，看选哪一个作为服务器，所以就有了一下的状态转移方程。（设 w 为选中的儿子）

但是这样的话，我们每次都还需要用 \cal O(n) 的时间复杂度来求和，会超时。

但是我们动动脑子，就会发现，dp[x][1] 不就是我们后面所求的那个和吗？那么我们直接用 dp[x][1] 把 \sum dp[v_i][2] 给替换了不就行了？

现在所有的答案都有了，那么我们最终的答案就是 \min(dp[1][0],dp[1][2])。

最后提一嘴，清空的时候要小心。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e5+10;
int dp[INF][3];
vector<int> mp[INF];

void dfs(int x,int fa){
    dp[x][0]=1,dp[x][1]=0,dp[x][2]=1e8;
    int len=mp[x].size();
    for (int i=0;i<len;i++){
        if (mp[x][i]==fa)continue;
        int t=mp[x][i];
        dfs(t,x);
        dp[x][0]+=min(dp[t][0],dp[t][1]);
        dp[x][1]+=dp[t][2];
    }
    if (len==1&&x!=1)return;
    for (int i=0;i<len;i++){
        if (mp[x][i]==fa)continue;
        int t=mp[x][i];
        dp[x][2]=min(dp[x][2],dp[t][0]+dp[x][1]-dp[t][2]);
    }
}
int main(){
    while (1){
        int n,t;
        cin>>n;
        for (int i=1;i<=n;i++){
            mp[i].clear();
        }
        for (int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
        dfs(1,-1);
        cout<<min(dp[1][0],dp[1][2])<<endl;
        cin>>t;
        if (t==-1)return 0;
    }
    return 0;
}