这道题只要树形dp做的熟练的话就能秒（显然我不能）。
令dp[u][0 / 1]表示u所在的子树和u相连的联通块没有/有敌人的最少代价。而且按题中所述，这个联通块只能有1个敌人。
分情况：
若敌人在节点u：
则dp[u][0] = INF，dp[u][1] = Σmin{dp[v][0], dp[v][1] + w[i]}。
若敌人不在u：
则dp[u][0] = Σmin{dp[v][0], dp[v][1] + w[i]}， dp[u][1] = Σmin{dp[v][0], dp[v][1] + w[i]} + dp[v'][1]。(v'∉{v})
只要一直记着一个联通块最多只能有一个敌人就行了。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const ll INF = 1e12; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) last = ch, ch = getchar(); 26 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, k; 38 bool vis[maxn], in[maxn]; 39 40 struct Edge 41 { 42 int nxt, to, w; 43 }e[maxn << 1]; 44 int head[maxn], ecnt = -1; 45 void addEdge(int x, int y, int w) 46 { 47 e[++ecnt] = (Edge){head[x], y , w}; 48 head[x] = ecnt; 49 } 50 51 ll dp[maxn][2]; 52 void dfs(int now, int _f) 53 { 54 if(vis[now]) dp[now][0] = INF; 55 in[now] = vis[now]; 56 ll sum = 0; 57 for(int i = head[now], v; i != -1; i = e[i].nxt) 58 { 59 v = e[i].to; 60 if(v == _f) continue; 61 dfs(v, now); 62 in[now] |= in[v]; 63 sum += min(dp[v][0], dp[v][1] + e[i].w); 64 } 65 if(vis[now]) dp[now][1] = sum; 66 else dp[now][0] = dp[now][1] = sum; 67 if(!vis[now]) for(int i = head[now], v; i != -1; i = e[i].nxt) 68 { 69 v = e[i].to; 70 if(v == _f || !in[v]) continue; 71 dp[now][1] = min(dp[now][1], sum - min(dp[v][0], dp[v][1] + e[i].w) + dp[v][1]); 72 } 73 } 74 75 int main() 76 { 77 Mem(head, -1); 78 n = read(); k = read(); 79 for(int i = 1; i <= k; ++i) {int x = read() + 1; vis[x] = 1;} 80 for(int i = 1; i < n; ++i) 81 { 82 int x = read() + 1, y = read() + 1, w = read(); 83 addEdge(x, y, w); addEdge(y, x, w); 84 } 85 dfs(1, 0); 86 write(min(dp[1][0], dp[1][1])), enter; 87 return 0; 88 }