张老师给的一道题，P2700逐个击破，用树形dp方法写的，最近第一次复习到树形dp，稍微mark一下qwq
用最小生成树的写法比较好想一些，有空可以实现一下（挖坑）
思路
dp[i][1]代表以i为根的子树，里面有一个敌军且合法，与之相对，dp[i][0]代表以i为根的子树，里面有没有敌军且合法
转移方程的思路即为：
我有敌军=min（我有敌军&&儿子没有，我有敌军&&儿子也有&&这条路去掉，我没有敌军我儿子有）
我无敌军=min（我无敌军&&我儿子无敌军，我无敌军&&儿子有敌军&&这条路去掉）
最后稍微注意一下long long就完了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int INF=0x3f3f3f;
bool st[N];
ll dp[N][2];
int pre[N],nex[N*2],edge[N*2],ver[N*2],tot;
void add(int x,int y,int z){
ver[++tot]=y;
edge[tot]=z;
nex[tot]=pre[x];
pre[x]=tot;
}
void dfs(int u,int fa){
if(st[u])dp[u][0]=INF;
for(int i=pre[u];i;i=nex[i]){
int v=ver[i];
if(v==fa)continue;
dfs(v,u);
dp[u][1]=min(dp[u][1]+dp[v][1]+edge[i],min(dp[u][0]+dp[v][1],dp[u][1]+dp[v][0]));
dp[u][0]=min(dp[u][0]+dp[v][1]+edge[i],dp[u][0]+dp[v][0]);
}
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++){
int x;
cin>>x;
st[x+1]=1;
}
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
add(x+1,y+1,z);
add(y+1,x+1,z);
}
dfs(1,-1);
cout<<min(dp[1][0],dp[1][1]);
}