记录编号	385653	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	3.272 s
提交时间	2017-03-22 08:45:49	内存使用	10.59 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char cc;int ff;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');
	if(cc=='-')ff=-1,cc=getchar();else ff=1;x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;if(ff<0)x=-x;
}
const int maxn=200005,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next,dis;}e[maxn<<1];
struct Rabit_Tree{
	int son,dis,black;
	bool operator < (const Rabit_Tree &a)const{
		return black<a.black;
	}
}t[maxn];
int n,K,m,head[maxn],len=1,ans=0;bool isb[maxn],vis[maxn];
int Sz,size[maxn],mx[maxn],RT,cot=0,Dep,Dp[maxn];
void Set(int prt,int son,int dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,e[len].dis=dis;
}
#define to e[i].to
void Get(int rt,int fa){
	size[rt]=1,mx[rt]=0;
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Get(to,rt),size[rt]+=size[to],mx[rt]=max(mx[rt],size[to]);
	mx[rt]=max(mx[rt],Sz-size[rt]);
	if(mx[rt]<mx[RT])RT=rt;
}
void Get(int rt,int fa,int bk,int &BK){
	if(bk>K)return;BK=max(bk,BK);
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Get(to,rt,bk+isb[to],BK);
}
void Run(int rt,int fa,int bk,int dis){
	if(bk>K)return;ans=max(ans,dis+Dp[min(K-bk,Dep)]);
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Run(to,rt,bk+isb[to],dis+e[i].dis);
}
void Dig(int rt,int fa,int bk,int dis){
	if(bk>K)return;Dp[bk]=max(Dp[bk],dis);
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Dig(to,rt,bk+isb[to],dis+e[i].dis);
}
void Get(int rt){
	cot=Dep=0;int i,j;
	for(i=head[rt];i;i=e[i].next)if(!vis[to])
		t[cot++]=(Rabit_Tree){to,e[i].dis,0},Get(to,0,isb[to],t[cot-1].black);
	sort(t,t+cot);
	for(i=0;i<cot;i++){
		Run(t[i].son,0,isb[t[i].son]+isb[rt],t[i].dis);
		Dig(t[i].son,0,isb[t[i].son],t[i].dis);
		Dep=t[i].black;
		for(j=1;j<=Dep;j++)Dp[j]=max(Dp[j],Dp[j-1]);
	}	
	for(i=0;i<=Dep;i++)Dp[i]=0;
}
void Run(int rt){
	vis[rt]=true;Get(rt);
	for(int i=head[rt];i;i=e[i].next)
		if(!vis[to])RT=0,Sz=size[to],Get(to,0),Run(RT);
}
void Rabit_in(){
	R_int(n),R_int(K),R_int(m);int i,x,y,z;
	while(m--)R_int(x),isb[x]=true;
	for(i=1;i<n;i++)R_int(x),R_int(y),R_int(z),Set(x,y,z),Set(y,x,z);
}
void Rabit_ans(){
	mx[RT=0]=INF,Sz=n,Get(1,0);
	Run(RT);printf("%d\n",ans);
}
int main(){
	freopen("freetourII.in","r",stdin);freopen("freetourII.out","w",stdout);
	Rabit_in();Rabit_ans();
	fclose(stdin);fclose(stdout);return 0;
}