题意：
给定一个有n个节点的无根树，有两种装置A和B，每种都有无限多个。在某个节点X使用A装置需要C1的花费，并且此时与节点X相连的边都被覆盖。在某个节点X使用B装置需要C2的花费，并且此时与节点X相连的边以及与X相连的点相连的边都被覆盖。求覆盖所有边的最小花费。
分析：
首先无根树可以先dfs确定根。考虑选择装置A和装置B的影响。
装置A只会影响节点u连出去的边。而装置B还会影响u相连的点相连的边，也就是说与节点u距离为2的边也会被影响。
也就是说，对于边(u,fa[u])，如果fa[fa[u]]装上装置B,那么这条边就被覆盖。但只有这种情况吗？有一个容易漏的情况就是如果u、v的父亲都是fa[u]，如果在v上装了装置B，那么边(u,fa[u])就被覆盖了。（像我这种想东西不全面的人就容易把这种情况漏掉，导致我后来整个代码重打了一遍~~）
而对于装置A，处理过程就相对简单了，下面我只说说我怎么处理装置B的。
用了个四维DP，dp[x][a][b][c](a=0~2; b=0~2; c=0~1)表示节点x，选了a装置(0表示不选，1表示装置A，2表示装置B)，fa[x]选了b装置，目前边(u,fa[u])的状态为c。
如果c=0，那么u的子节点中一定要有至少一个装上装置B。而对于上述说的装置B的第二种情况，我们也可以用这个一起计算。
那么就是两种方案：
1、u的子节点中至少有一个装上装置B。
2、u的子节点中没有装上装置B的。
当符合条件时，取两者的min值即可。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 10010
#define INF 100000010 int dp[Maxn][][][];
int first[Maxn],fa[Maxn];
int n,c1,c2; struct node
{
int x,y,next;
}t[*Maxn];int len; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} int mymin(int x,int y) {return x<y?x:y;} void dfs(int x,int f)
{
fa[x]=f;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
dfs(y,x);
}
} int ffind(int x,int a,int b,int c)// a->x b->fa c->(x,fa[x])
{
if(dp[x][a][b][c]<INF) return dp[x][a][b][c];
int ans=dp[x][a][b][c];
int p=(a!=||b==)?:,h=,y,now;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])//sons have at least one B
{
y=t[i].y;
now=mymin(mymin(ffind(y,,a,),ffind(y,,a,)),ffind(y,,a,));
h+=now;
}
for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])
{
y=t[i].y;
now=mymin(mymin(ffind(y,,a,),ffind(y,,a,)),ffind(y,,a,));
ans=mymin(ans,h-now+ffind(y,,a,));
}
if(c!=) //sons have no B
{
now=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])
{
y=t[i].y;
now+=mymin(ffind(y,,a,p),ffind(y,,a,));
}
ans=mymin(ans,now);
}
if(a==) ans+=c1;
else if(a==) ans+=c2;
dp[x][a][b][c]=ans;
return ans;
} int main()
{
while()
{
scanf("%d%d%d",&n,&c1,&c2);
if(n==&&c1==&&c2==) break;
len=;
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
memset(dp,,sizeof(dp));
dfs(,);
int ans=INF;
ans=mymin(ans,ffind(,,,));
ans=mymin(ans,ffind(,,,));
ans=mymin(ans,ffind(,,,));
printf("%d\n",ans);
}
return ;
}
UVA12093
2016-03-10 17:16:10