JZOJ 2678. 树B

题目

Description

已知无向连通图G由N个点，N-1条边组成。每条边的边权给定。现要求通过删除一些边，将节点1与另M个指定节点分开，希望删除的边的权值和尽量小，求此最小代价。

Input

每个输入文件中仅包含一个测试数据。

第一行包含两个整数N,M。

第二行至第N行每行包含3个整数,A、B、C，表示节点A与节点B有一条边相连，边权为C。

第N+1行至第N+M行每行包含一个整数X，表示要求与节点1分开的节点。

Output

输出文件仅包含一个整数，表示最小代价。

Sample Input

Sample Output

Data Constraint

Hint

对于20%的数据，2<=N<=10

对于100%的数据，2<=N<=10^6

分析

树形DP
设f[x]表示以x为根节点删除我需要点的最小值
f[x]+=min(f[y],map[x][y])

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int u,v,w,nx;
 5 }g[1000011*2];
 6 int cnt;
 7 int li[1000001*2];
 8 void add(int u,int v,int w) 
 9 {
10     g[++cnt].u=u; g[cnt].v=v; g[cnt].w=w; g[cnt].nx=li[u]; li[u]=cnt;
11     g[++cnt].u=v; g[cnt].v=u; g[cnt].w=w; g[cnt].nx=li[v]; li[v]=cnt;
12 }
13 int flag[1000001];
14 int dp[1000001];
15 int b[1000001];
16 void dfs(int x)
17 {
18     int ff=0;
19     flag[x]=1;
20     for (int i=li[x];i;i=g[i].nx)
21     {
22         int y=g[i].v;
23         if (!flag[y])
24         {
25             if (b[g[i].v])
26               ff+=g[i].w;
27             else
28             {
29                 dfs(y);
30                 ff+=min(dp[y],g[i].w); 
31             }
32         }
33     }
34     dp[x]=ff;
35 }
36 int main  ()
37 {
38     int n,m;
39     cin>>n>>m;
40     for (int i=1,x,y,z;i<=n-1;i++)
41     {
42         cin>>x>>y>>z;
43         add(x,y,z);
44     }
45     for (int i=1,x;i<=m;i++)
46     {
47         cin>>x;
48         b[x]=1;
49     }
50     memset(dp,0x3f,sizeof(dp));
51     dfs(1);
52     cout<<dp[1];
53 }

为何要逼自己长大，去闯不该闯的荒唐