http://acm.hdu.edu.cn/showproblem.php?pid=4313

1
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

10
Hint
Neo can destroy the road connecting city 2 and city 4 of weight 5 , and the road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a
time, the total minimum time taken is 10 units of time. After destroying these roads none of the Machines can reach other Machine via any path.
 

/**
hdu 4313   并查集+贪心
题目大意：
         给定n（n<=100000）个节点的树，每条边有一定的权值，有m个点是危险的，现在想将树分成m块使得每块中恰好只有一个危险的点，问最小的花费是多少。
解题思路：
         类似Kruskal的贪心过程，将节点按照从小到大排序，以每个危险的节点为并查集的根节点

*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int maxn=100005;

struct note
{
    int u,v;
    LL w;
    bool operator < (const note &other) const
    {
        return w>other.w;
    }
} edge[maxn];

int father[maxn];
bool flag[maxn];
int n,m;

void init()
{
    for(int i=0; i<=n; i++)
    {
        father[i]=i;
    }
}

int find(int u)
{
    if(u==father[u])
        return u;
    return father[u]=find(father[u]);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n-1; i++)
        {
            int u,v;
            LL w;
            scanf("%d%d%I64d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        memset(flag,false,sizeof(flag));
        for(int i=0; i<m; i++)
        {
            int u;
            scanf("%d",&u);
            flag[u]=true;
        }
        init();
        LL sum=0;
        sort(edge,edge+n-1);
        for(int i=0; i<n-1; i++)
        {
            int x=find(edge[i].u);
            int y=find(edge[i].v);
            if(flag[x]&&flag[y])
            {
                sum+=edge[i].w;
            }
            else if(flag[x])
            {
                father[y]=x;
            }
            else
            {
                father[x]=y;
            }
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

/**
hdu 4313  树形dp
题目大意：
         给定n（n<=100000）个节点的树，每条边有一定的权值，有m个点是危险的，现在想将树分成m块使得每块中恰好只有一个危险的点，问最小的花费是多少。
解题思路：
         dp[i][0]代表的是在当前以i节点为根节点的子树中，i所在的连通块中没有危险节点的最小花费；
         dp[i][1]代表的是在当前以i节点为根节点的子树中，i所在的连通块中有危险节点的最小花费；
         如果i是叶子节点：如果i为危险点dp[i][0] = inf，dp[i][1]= 0；否则dp[i][0] = 0,dp[i][1] = inf；
         如果i不是叶子节点：如果i是危险点dp[i][0] = inf , dp[i][1] = sigma min（dp[son][0]，dp[son][1]+w）；
         否则dp[i][0] = sigma min（dp[son][0]，dp[son][1]+w），dp[i][1] = min（dp[i][0] – min（dp[son][0]，dp[son][1]+w）+dp[son][1]）。

*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int maxn=100005;
const LL inf=0x3fffffffffffffffLL;

int head[maxn],ip;
LL dp[maxn][2];
int n,m;
bool flag[maxn];

struct note
{
    int v,next;
    LL w;
} edge[maxn*2];

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

void addedge(int u,int v,LL w)
{
    edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++;
}

void dfs(int u,int pre)
{
  ///  printf("%d->%d\n",pre,u);
    if(flag[u])
    {
        dp[u][0]=inf;
        dp[u][1]=0;
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            LL w=edge[i].w;
            if(v==pre)continue;
            dfs(v,u);
            dp[u][1]+=min(dp[v][0],dp[v][1]+w);
        }
        return;
    }
    else
    {
        dp[u][0]=0;
        dp[u][1]=inf;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            LL w=edge[i].w;
            if(v==pre) continue;
            dfs(v,u);
            dp[u][0]+=min(dp[v][0],dp[v][1]+w);
        }
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            LL w=edge[i].w;
            if(v==pre)continue;
            dp[u][1]=min(dp[u][1],dp[u][0]-min(dp[v][0],dp[v][1]+w)+dp[v][1]);
        }
        return;
    }
}
/**void dfs1(int u,int pre)
{
    printf("%d->%d\n",pre,u);
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)continue;
        dfs1(v,u);
    }
}*/
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1; i<n; i++)
        {
            int u,v;
            LL w;
            scanf("%d%d%I64d",&u,&v,&w);
            u++;
            v++;
            addedge(u,v,w);
            addedge(v,u,w);
          //  printf("%d-->%d\n",u,v);
           // printf("%d-->%d\n",v,u);

        }
        memset(flag,false,sizeof(flag));
        for(int i=0; i<m; i++)
        {
            int x;
            scanf("%d",&x);
            x++;
            flag[x]=true;
        }
        dfs(1,-1);
        //dfs1(1,-1);
        /**for(int i=1;i<=n;i++)
        {
            printf("%d %I64d %I64d\n",i,dp[i][0],dp[i][1]);
        }*/
        printf("%I64d\n",min(dp[1][0],dp[1][1]));
    }
    return 0;
}

hdu4313 贪心并查集 || 树形dp