Wunder Fund Round 2016 D. Hamiltonian Spanning Tree

分析：树形DP
主要看x

$dp[u][0]$：如果$u$的子节点中有$dp[v_1][1]+dp[v_2][1]<=dp[v_1][0]+dp[v_1][0]$的，那么$dp[u][0]=dp[u][1]-1$，不然$dp[u][0] = dp[u][1]$

代码：

#include using namespace std;#define FOR(i,x,y)  for(int i = x;i < y;++ i) 
#define IFOR(i,x,y) for(int i = x;i > y;-- i) 
#define pb  push_backtypedef long long LL;
typedef vector <int>    VI;const int maxn = 200010;
const int inf = 1<<30;int dp[maxn][2],du[maxn],n;
LL x,y;VI mat[maxn];void dfs(int u,int fa){int minx = inf;int num = 0,sum = 0;FOR(i,0,(int)mat[u].size()){int v = mat[u][i];if(v == fa) continue;dfs(v,u);if(dp[v][0] == dp[v][1])    num ++;sum += dp[v][0];minx = min(dp[v][1]-dp[v][0],minx);}if(minx == inf) dp[u][1] = 1;else    dp[u][1] = minx + sum;if(num >= 2)    dp[u][0] = dp[u][1]-1;else    dp[u][0] = dp[u][1];//printf("id:%d\t dp[u][0]:%d\t dp[u][1]:%d\n",u,dp[u][0],dp[u][1]);
}int main(){scanf("%d%I64d%I64d",&n,&x,&y);FOR(i,0,n+1)    mat[i].clear(),du[i] = 0;;FOR(i,1,n){int u,v;    scanf("%d%d",&u,&v);mat[u].pb(v);   mat[v].pb(u);du[u] ++;   du[v] ++;}if(x >= y){bool flag = false;FOR(i,1,n+1) if(du[i] == n-1) {flag = true;break;}if(flag){printf("%I64d\n",y*(n-2)+x);}else{printf("%I64d\n",y*(n-1));}}else{dfs(1,-1);printf("%I64d\n",(dp[1][0]-1)*y+(n-dp[1][0])*x);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！