题面
题目链接
题解
这题第一眼就是个树形DP，题目其实已经告诉了我们这就是一棵树，因为任意两个黑点不能联通，所以要保证每个点最多连接一个黑点（无论是直接或间接或自己是黑点），所以可进行转移。
设f[i][0]表示这个点不连接任何黑点是的最小代价，f[i][1]表示这个点有且仅有一个相连的黑点时的代价，则易得转移方程为：
f
[
i
]
[
0
]
=
∑
s
o
n
i
m
i
n
(
f
[
s
o
n
]
[
0
]
,
f
[
s
o
n
]
[
1
]
+
s
i
d
e
[
x
]
.
s
u
m
)
f_{[i][0]}=\sum_{son}^i min(f_{[son][0]},f_{[son][1]+side[x].sum})
f[i][0]=∑sonimin(f[son][0],f[son][1]+side[x].sum)
f
[
i
]
[
1
]
=
(
∑
s
o
n
i
m
i
n
(
f
[
s
o
n
]
[
0
]
,
f
[
s
o
n
]
[
1
]
+
s
i
d
e
[
x
]
.
s
u
m
)
)
−
m
i
n
(
m
i
n
(
f
[
s
o
n
]
[
0
]
,
f
[
s
o
n
]
[
1
]
+
s
i
d
e
[
x
]
.
s
u
m
)
−
m
i
n
(
f
[
s
o
n
]
[
0
]
,
f
[
s
o
n
]
[
1
]
)
)
f_{[i][1]}=(\sum_{son}^i min(f_{[son][0]},f_{[son][1]+side[x].sum}))-min(min(f_{[son][0]},f_{[son][1]+side[x].sum})-min(f_{[son][0]},f_{[son][1]}))
f[i][1]=(∑sonimin(f[son][0],f[son][1]+side[x].sum))−min(min(f[son][0],f[son][1]+side[x].sum)−min(f[son][0],f[son][1]))
注意
若当前节点是黑点，则f[i][0]=INF，f[i][1]不能减去min(f_{[son][0]},f_{[son][1]})。
代码如下
using namespace std;
int i,j,n,m,k,l,o,p,st[100005],a[100005],fa[100005];
long long f[100005][2];//DP数组
struct node
{
long long sum;
int nxt,to;
};//链式前向星
node side[200005];
void find(int w)
{
long long maxi=0;
for (int x=st[w];x!=0;x=side[x].nxt)
{
int y=side[x].to;
if (fa[y]==0)
{
fa[y]=x;//标记
find(y);
f[w][1]+=min(side[x].sum+f[y][1],f[y][0]);
maxi=max(maxi,min(side[x].sum,f[y][0]-f[y][1]));//DP方程
if (f[w][0]<21147483647483647)
{
f[w][0]+=min(side[x].sum+f[y][1],f[y][0]);
}//判断当前点是否为黑点
}
}
if (f[w][0]!=21147483647483647) f[w][1]-=maxi;//判断当前点是否为黑点
}
int main()
{
fa[1]=1;
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d",&a[i]);
a[i]++;
f[a[i]][0]=21147483647483647;//黑点标记成+INF
}
for (i=1;i<n;i++)
{
scanf("%d %d %d",&o,&p,&l);
o++;
p++;
side[i*2-1].to=p;
side[i*2-1].sum=l;
side[i*2-1].nxt=st[o];
st[o]=i*2-1;
side[i*2].to=o;
side[i*2].sum=l;
side[i*2].nxt=st[p];
st[p]=i*2;
}//链式前向星存图
find(1);
printf("%lld",min(f[1][0],f[1][1]));//花费最小的方案
}
码风有点丑，请见谅。
