## 代码
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int nma=100005;
int n,m;
int fa[nma],so[nma],bo[nma],fdis[nma];
bool en[nma];
int cod[nma],cos[nma];
int i,j,x,y,z;
void link(int x,int y,int z){
if(fa[y]) link(y,fa[y],fdis[y]);
fa[y]=x; fdis[y]=z;
return;
}
void calculate(int p){
for(int ion=so[p];ion;ion=bo[ion]){
calculate(ion);
}
if(en[p]){
cod[p]=fdis[p];
for(int ion=so[p];ion;ion=bo[ion]){
cos[p]+=cod[ion]+cos[ion];
}
}
else{
int dma=0;
for(int ion=so[p];ion;ion=bo[ion]){
cod[p]+=cod[ion];
cos[p]+=cos[ion]+cod[ion];
if(dma<cod[ion]) dma=cod[ion];
}
cos[p]-=dma;
if(cod[p]>fdis[p]) cod[p]=fdis[p];
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d",&x);
if(!x) x=n;
en[x]=1;
}
for(i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
if(!x) x=n;
if(!y) y=n;
link(x,y,z);
}
for(i=1;i<=n;i++){
bo[i]=so[fa[i]];
so[fa[i]]=i;
}
for(i=1;fa[i];i++) ;
calculate(i);
printf("%lld",cos[i]);
return 0;
}
```
by qjyzLfy @ 2020-01-30 15:38:47
## 思路
树形DP。
**1，** 转化成任意有根树。
**2，** 从下往上，计算每个子树的：
1.使该子树上所有有敌军的点都与主树脱离，需要的最小代价（ _拆除代价_ ）； 2.使该子树内部有敌军的点相互分离，需要的最小代价（ _解构代价_ ）。
**3，** 输出根节点的解构代价。
by qjyzLfy @ 2020-01-30 15:47:27
## 变量的含义
```
fa[p] p的父亲.
so[p] p的一个儿子
bo[p] p的一个兄弟
(用邻接表存树)
fdis[p] p到它父亲的距离
en[p] p点是否有敌军
cod[p] p的拆除代价
cos[p] p的解构代价
dma 子树中cod的最大值
```
by qjyzLfy @ 2020-01-30 15:54:08
## 转移方程
**如果 p 点有敌军：**
`cod[p]=fdis[p]` 因为p必须与主树脱离.
`cos[p]`为 p 所有子节点拆除代价与解构代价之和.
**如果 p 点没有敌军：**
`cod[p]`为 p 所有子节点拆除代价之和 或 `fdis[p]`(取较小者);
`cos[p]`为 p 所有子节点拆除代价与解构代价之和,但拆除代价最大的子节点的拆除代价除外.因为有只有一颗子树与 p 相连依然满足 p 被解构.
by qjyzLfy @ 2020-01-30 16:04:55
~~我写得都比题解还详细了,~~ 就帮我看看吧!
by qjyzLfy @ 2020-01-30 16:06:44
0回复惨案,还好我自己找到了......
```
6 5
0 1 2 4 5
1 2 10
2 3 1000
3 4 10
3 5 10
3 0 10
```
正解 40 ; 输出 60 (拆除代价与解构代价有交集)
by qjyzLfy @ 2020-01-30 23:22:49