记录编号	223272	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	15.078 s
提交时间	2016-02-08 23:57:24	内存使用	18.42 MiB

/*
Problem:spoj1825;
Language:c++;
by dydxh;
2015.7.26;
*/
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<utility>
using namespace std;
const int maxn=400005;
const int oo=2000000000;
int n,m,K,cnt=0,max_siz,root,ans=0,total;
int linkk[maxn],siz[maxn],black[maxn],f[maxn],g[maxn],son[maxn];
bool col[maxn],vis[maxn];
struct edge{
	int v,y,next;
}e[maxn<<1];
inline int read(){
    int x=0;bool flag=false;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') flag=true;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return flag?-x:x;
}
void insert(int a,int b,int c){
	e[++cnt].y=b,e[cnt].next=linkk[a],linkk[a]=cnt,e[cnt].v=c;
	e[++cnt].y=a,e[cnt].next=linkk[b],linkk[b]=cnt,e[cnt].v=c;
}
bool mycmp(int a,int b){return black[e[a].y]<black[e[b].y];}
void get_siz(int x,int fa){
	siz[x]=1;
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==fa || vis[tn]) continue;
		get_siz(tn,x);
		siz[x]+=siz[tn];
	}
}
void get_root(int x,int fa){
	int now_siz=0;
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==fa || vis[tn]) continue;
		get_root(tn,x);
		if(now_siz<siz[tn]) now_siz=siz[tn];
	}
	if(total-siz[x]>now_siz) now_siz=total-siz[x];
	if(max_siz>now_siz) max_siz=now_siz,root=x;
}
void get_black(int x,int fa){
	int ack=col[x];
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==fa || vis[tn]) continue;
		get_black(tn,x);
		ack+=black[tn];
	}
	black[x]=ack;
}
void get_g(int x,int fa,int dis,int ack){
	if(g[ack]<dis) g[ack]=dis;
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==fa || vis[tn]) continue;
		get_g(tn,x,dis+e[i].v,ack+col[tn]);
	}
}
void sol(int x){
	get_siz(x,x);
	max_siz=oo;total=siz[x];
	get_root(x,x);
	int rot=root;
	vis[rot]=1;
	for(int i=linkk[rot];i;i=e[i].next){
		int tn=e[i].y;
		if(vis[tn]) continue;
		sol(tn);
	}
	int tot_son=0;
	for(int i=linkk[rot];i;i=e[i].next){
		int tn=e[i].y;
		if(vis[tn]) continue;
		get_black(tn,rot);
		son[++tot_son]=i;
	}
	sort(son+1,son+1+tot_son,mycmp);
	for(int i=0;i<=black[e[son[tot_son]].y];i++) f[i]=-oo;
	for(int i=1;i<=tot_son;i++){
		int node=e[son[i]].y,v=e[son[i]].v;
		for(int j=0;j<=black[node];j++) g[j]=-oo;
		get_g(node,rot,v,col[node]);
		if(i!=1){
			for(int j=0;j<=K-col[rot] && j<=black[node];j++){
				int ex_;
				if(K-col[rot]-j<black[e[son[i-1]].y]) ex_=K-col[rot]-j;
				else ex_=black[e[son[i-1]].y];
				if(g[j]!=-oo && g[j]+f[ex_]>ans)
					ans=g[j]+f[ex_];
			}
		}
		for(int j=0;j<=black[node] && j<=K-col[rot];j++){
			if(g[j]>f[j]) f[j]=g[j];
			if(j && f[j-1]>f[j]) 
				f[j]=f[j-1];
			if(f[j]>ans) ans=f[j];
		}
	}
	vis[rot]=0;
}
int main(){
    //srand(time(0));
	freopen("freetourII.in","r",stdin);
	freopen("freetourII.out","w",stdout);
	n=read(),K=read(),m=read();
	for(int i=1;i<=m;i++) col[read()]=1;
	for(int i=1;i<n;i++){
		int a=read(),b=read(),c=read();
		insert(a,b,c);
	}
	sol(1);
	cout<<ans<<endl;
    //cout<<"Time has passed:"<<1.0*clock/1000<<"s!"<<endl;
    return 0;
}