 /**//*
題意:一棵樹,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;
}
|