 /**//*
题意:一棵树,A机器人能保护邻接的边及邻接点的邻接边 B机器人只能保护邻接的边
A,B机器人花费不同 求最小的代价保护所有的边
状态:
A[u]: u的父边、爷爷边,及子树都能被保护 costA+∑min(A[v],B[v],C[v],D[v])
B[u]: u的父边,及子树都能被保护
两种情况:u放一个机器人B costB+∑min(A[v],B[v],C[v])
至少一个v放一个机器人A ∑min(A[v],B[v],C[v])(至少一个A)
C[u]: u的子树都能被保护
解题报告是直接 ∑min(A[v],B[v])
我觉得有一种情况是某个v有A,有些有C,这样就可以覆盖到了
D[u]: u的某些儿子的边能被保护,但儿子的子树能被保护 ∑min(B[v],C[v])
*/
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 10010;
const int INF = 1000000000;

vector<int>G[MAXN];
int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int costA,costB,n;

void dfs(int u,int p)
  {
A[u]=costA;
B[u]=0;
C[u]=0;
D[u]=0;
int son=0;
bool flagB=true;
int cntC=0,cntA=0;
for(int i=0,size=G[u].size();i<size;i++)
 {
int v=G[u][i];
if(v==p)continue;
dfs(v,u);
A[u]+=min(min(A[v],B[v]),min(C[v],D[v]));
if(A[v]<min(B[v],C[v]))flagB=false;
B[u]+=min(A[v],min(B[v],C[v]));
if(A[v]<B[v]&&A[v]<C[v])cntA++;
if(C[v]<B[v]&&C[v]<A[v])cntC++;
C[u]+=min(A[v],min(B[v],C[v]));
D[u]+=min(B[v],C[v]);
}
if(flagB)//没有A时
 {
int Min=INF;
for(int i=0,size=G[u].size();i<size;i++)
 {
int v=G[u][i];
if(v==p)continue;
Min=min(Min,A[v]-min(B[v],C[v]));//选择一个A
}
B[u]+=min(Min,costB);//点u放机器人B
}
if(cntC&&!cntA)//如果有C但没有A时
 {
int Min=INF,tot=0;
for(int i=0,size=G[u].size();i<size;i++)
 {
int v=G[u][i];
if(v==p)continue;
 if(C[v]<B[v]) {tot+=B[v]-C[v];}//可以将全部的C换为B
Min=min(Min,A[v]-min(B[v],C[v]));//可以选择一个A
}
C[u]+=min(Min,tot);
}
//printf("%d %d %d %d %d\n",u,A[u],B[u],C[u],D[u]);
}
int main()
  {
//freopen("in","r",stdin);
while(scanf("%d%d%d",&n,&costB,&costA),n)
 {
for(int i=1;i<=n;i++)
G[i].clear();
for(int i=1,v,u;i<n;i++)
 {
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
printf("%d\n",min(min(A[1],B[1]),C[1]));
}
return 0;
}
|