P2700 逐个击破

题意：现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，

　　　现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开；

　　　

简单来说，就是把一棵树分成k个联通块，使得每个标记点独在一个联通块的最小删边代价

考虑并查集

虽然不能删边，但是可以逆向加边

跑最大生成树，如果当前边连接的两个城市不都是enemy，就加边，并让并查集合并

注：若两个集合的代表元素有一个是enemy，那么新集合的代表也是enemy

也就是说，当前集合有一个enemy，就把整个集合标记为enemy，这样就可以了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cmath>

using namespace std;

#define olinr return

#define _ 0

#define love_nmr 0

#define int long long

#define DB double

inline int read()

{

    int x=,f=;

    char ch=getchar();

    while(!isdigit(ch))

    {

        if(ch=='-')

            f=-f;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*f;

}

inline void put(int x)

{

    if(x<)

    {

        x=-x;

        putchar('-');

    }

    if(x>)

        put(x/);

    putchar(x%+'');

}

int n;

int k;

bool vis[];

struct node

{

    int x;

    int y;

    int dis;

    friend bool operator < (const node &a,const node &b)

    {

        return a.dis>b.dis;

    }

}edge[];

int fa[];

int tot;

int ans;

inline int findset(int x)

{

    return x==fa[x]? fa[x]:fa[x]=findset(fa[x]);

}

double eps=1e-;

signed main()

{

    n=read();

    k=read();

    for(int i=;i<=k;i++)

        vis[read()]=true;

    for(int i=;i<=n;i++)

        fa[i]=i;

    for(int i=;i<=n-;i++)

    {

        edge[i].x=read();

        edge[i].y=read();

        edge[i].dis=read();

        tot+=edge[i].dis;

    }

    sort(edge+,edge+n);

    for(int i=;i<=n-;i++)

    {

        int xx=findset(edge[i].x);

        int yy=findset(edge[i].y);

        if(!(vis[xx]&&vis[yy]))

        {

            fa[xx]=yy;

            if(vis[xx]||vis[yy])

                vis[xx]=vis[yy]=true;

            tot-=edge[i].dis;

        }

    }

    put(tot);

    olinr ~~(^_^)+love_nmr;

}