在一棵点有点权的树上,选择一些点,这些点能将所有与它们相连的点覆盖,最终将整棵树上的点全部覆盖,试求最小代价
1.u节点被自己覆盖,即选择u点来覆盖u点
2.u节点被儿子v覆盖,即选择v点来覆盖u点
3.u节点被父亲fa覆盖,即选择fa点来覆盖u点
//洛谷 2458
//花费最少覆盖所有点
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1505;
struct N{
int v,nxt;
}ed[maxn<<2];
int cnt,n;
int w[maxn],head[maxn<<2];
int dp[maxn][4],size[maxn],du[maxn];
//dp[i][0]选择本身来覆盖i点 dp[i][1]通过儿子来覆盖i点
//dp[i][2]通过父亲来覆盖i点
void add(int u,int v){
cnt++;
ed[cnt].v = v;
ed[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u,int fa){
dp[u][0] = w[u];
int sum=0,extr=0x7ffffff;
for(int v,i=head[u];i;i=ed[i].nxt){
v = ed[i].v;
if(v==fa)continue;
dfs(v,u);
dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
// 选择本身覆盖u点 则儿子状态任意,取最小即可
dp[u][1]+=min(dp[v][0],dp[v][1]);
if(dp[v][0]<dp[v][1])sum++;
else extr = min(dp[v][0]-dp[v][1],extr);
//选择u的儿子覆盖u
//儿子不通过父亲被覆盖有两种方式 自身和儿子的儿子
//若每次都选择儿子的儿子 就要再加上min(dp[v][0]-dp[v][1])使得u被儿子覆盖
dp[u][2]+=min(dp[v][0],dp[v][1]);
//选择父亲覆盖u点 则u的儿子需要被覆盖
}
if(!sum)dp[u][1]+=extr;
}
int main() {
int m,v,u;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&u);
scanf("%d",&w[u]);
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d",&v);
add(u,v); add(v,u);
}
}
dfs(1,0);
printf("%d\n",min(dp[1][0],dp[1][1]));
return 0;
}