记录编号	364493	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	4.563 s
提交时间	2017-01-16 19:54:18	内存使用	11.98 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=201000;
struct edge{int to,next,dis;}e[maxn*2];
int tot,head[maxn];
void add(int u,int  v,int w){
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].next=head[u];
	head[u]=tot;
}
int size[maxn],f[maxn],root;
int n,cnt,m,k,ans,c[maxn];
int max_s[maxn],d[maxn],dis[maxn];
int q[maxn],mx,t[maxn];
bool vis[maxn];
#define to e[i].to
void get_root(int u,int fa){
	f[u]=0,size[u]=1;
	for(int i=head[u];i;i=e[i].next){
		if(to==fa||vis[to])continue;
		get_root(to,u);
		size[u]+=size[to];
		f[u]=max(f[u],size[to]);
	}
	f[u]=max(f[u],cnt-size[u]);
	if(!root || f[u]<f[root]) root=u;
}
void get_deep(int u,int fa,int rt){
	max_s[rt]=max(max_s[rt],d[u]);
	for(int i=head[u];i;i=e[i].next){
		if(to==fa||vis[to])continue;
		d[to]=d[u]+c[to];
		dis[to]=dis[u]+e[i].dis;
		get_deep(to,u,rt);
	}
}
void calc(int u,int fa,int rt){
	if(!c[rt]&&d[u]<=k){
		if(k-d[u]<=mx)ans=max(ans,t[k-d[u]]+dis[u]);
		else ans=max(ans,t[mx]+dis[u]);
	}else if(c[rt]&&d[u]<k){
		if(k-1-d[u]<=mx)ans=max(ans,t[k-1-d[u]]+dis[u]);
		else ans=max(ans,t[mx]+dis[u]);
	}
	for(int i=head[u];i;i=e[i].next)
		if(to!=fa&&!vis[to]) calc(to,u,rt);
}
void add2(int u,int fa,int flag){
	if(d[u]<=k){
		if(flag) t[d[u]]=max(t[d[u]],dis[u]);
		else t[d[u]]=0;
	}
	for(int i=head[u];i;i=e[i].next)
		if(to!=fa&&!vis[to])add2(to,u,flag);
}
bool cmp(int a,int b){return max_s[a]<max_s[b];}
void dfs(int u){
	vis[u]=1;int res=0;
	for(int i=head[u];i;i=e[i].next){
		if(vis[to])continue;
		d[to]=c[to],dis[to]=e[i].dis;
		get_deep(to,0,to),q[++res]=to;
	}
	sort(q+1,q+res+1,cmp);
	for(int i=1;i<=res;i++){
		calc(q[i],0,u);add2(q[i],0,1);
		mx=min(max_s[q[i]],k);
		for(int j=1;j<=mx;j++)t[j]=max(t[j],t[j-1]);
	}
	for(int i=1;i<=res;i++){
		add2(q[i],0,0);
		for(int j=1;j<=min(k,max_s[q[i]]);j++)t[j]=0;
	}
	for(int i=head[u];i;i=e[i].next){
		if(vis[to])continue;
		cnt=size[to],root=0;
		get_root(to,0);dfs(root);
	}
}
int main(){
	freopen("freetourII.in","r",stdin);freopen("freetourII.out","w",stdout);
	cnt=n=read(),k=read(),m=read();
	for(int i=1,x;i<=m;i++)x=read(),c[x]=1;
	for(int i=1;i<n;i++){
		int a=read(),b=read(),c=read();
		add(a,b,c);add(b,a,c);
	}
	get_root(1,0);dfs(root);
	printf("%d\n",ans);	
	fclose(stdin);fclose(stdout);
	return 0;
}