生活随笔
收集整理的這篇文章主要介紹了
[树形DP | Uva 1218]Perfect Service
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
dp[i][0]表示以i為根的且i被選為服務(wù)器的最小服務(wù)器數(shù)
dp[i][1]表示以i為根且i不被選為服務(wù)器，而i父親為服務(wù)器的最小服務(wù)器數(shù)
dp[i][2]表示以i為根且i不被選為服務(wù)器，而i父親也不被選為服務(wù)器的最小服務(wù)器數(shù)
dp[i][0] = Sum(max(dp[j][0],dp[j][1]) + 1
dp[i][1] = Sum(dp[j][2])
dp[i][2] = min(dp[i][1] - dp[j][2] + dp[j][0])
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N
= 1e4 + 5;
typedef long long ll
;
const int INF
= 1e5 + 5;
const ll LLINF
= (1LL<<60);
using namespace std
;
const int mod
= 998244353;
ll
fast_pow(ll a
,ll b
){ll ans
= 1;while(b
){if(b
&1)ans
= (ans
* a
)%mod
;a
= (a
* a
)%mod
;b
>>=1;}return (ans
%mod
);
}
typedef pair
<int,int> pii
;
int n
;
vector
<int> g
[N
];
int dp
[N
][3];
void dfs(int u
,int f
){if(g
[u
].size() == 1 && g
[u
][0] == f
){return;}for(int i
= 0;i
< g
[u
].size();i
++){int v
= g
[u
][i
];if(v
== f
)continue;dfs(v
,u
);dp
[u
][0] += min(dp
[v
][0],dp
[v
][1]);dp
[u
][1] += dp
[v
][2];}for(int i
= 0;i
< g
[u
].size();i
++){int v
= g
[u
][i
];if(v
== f
)continue;dp
[u
][2] = min(dp
[u
][1] - dp
[v
][2] + dp
[v
][0],dp
[u
][2]);}}
int main(){
#if DBGfreopen("input.txt","r",stdin);
#endifwhile(cin
>>n
){for(int i
= 1;i
<= n
;i
++){g
[i
].clear();dp
[i
][0] = 1,dp
[i
][1] = 0; dp
[i
][2] = INF
;}for(int i
= 1;i
<= n
- 1;i
++){int u
,v
;scanf("%d%d",&u
,&v
);g
[u
].pb(v
);g
[v
].pb(u
);}int end
;scanf("%d",&end
);dfs(1,-1);int ans
= min(dp
[1][0],dp
[1][2]);printf("%d\n",ans
);if(end
== -1)break;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的[树形DP | Uva 1218]Perfect Service的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
