记录编号	274990	评测结果	AAAAAAAAAAAAAAAAAAAAT
题目名称	[SPOJ 1825] 免费旅行II	最终得分	95
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	15.922 s
提交时间	2016-06-30 19:27:10	内存使用	26.64 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=400010;
const int INF=2147483647;
int n,m,k,c[maxn];
int cnt,fir[maxn],nxt[maxn*2],to[maxn*2],val[maxn*2];
void addedge(int a,int b,int v){
	nxt[++cnt]=fir[a];
	fir[a]=cnt;
	val[cnt]=v;
	to[cnt]=b;
}

bool vis[maxn];
int N,rt,sz[maxn],son[maxn];
void Get_RT(int x,int fa){
	sz[x]=1;son[x]=0;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa&&!vis[to[i]]){
			Get_RT(to[i],x);
			sz[x]+=sz[to[i]];
			son[x]=max(son[x],sz[to[i]]);
		}
	son[x]=max(son[x],N-sz[x]);
	if(!rt||son[x]<son[rt])rt=x;	
}

int st[maxn],stot;
int pt[maxn],ptot;
int tmp[maxn];

int dis[maxn],sum[maxn];

void DFS(int x,int fa){
	pt[++ptot]=x;
	for(int i=fir[x];i;i=nxt[i])
		if(!vis[to[i]]&&to[i]!=fa){
			dis[to[i]]=dis[x]+val[i];
			sum[to[i]]=sum[x]+c[to[i]];
			DFS(to[i],x);
		}
}

bool cmp(int x,int y){
	if(sum[x]!=sum[y])
	return sum[x]<sum[y];
	return dis[x]>dis[y];
}

void Get(int *q,int &tot){
	int p=0;
	sort(q+1,q+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		if(p&&dis[q[i]]<=dis[tmp[p]])continue;
		tmp[++p]=q[i];
	}
	for(int i=1;i<=p;i++)q[i]=tmp[i];
	tot=p;
}

int Get_Max(int x,int d,int v){
	ptot=0;
	dis[x]=d;
	sum[x]=c[x];
	
	DFS(x,0);
	Get(pt,ptot);
	
	int l=1,r=ptot,ret=-INF;
	while(l<=stot&&r>=1){
		if(sum[st[l]]+sum[pt[r]]>k)r--;
		else ret=max(ret,dis[st[l]]+dis[pt[r]]),l+=1;
	}
	
	for(int i=1;i<=ptot;i++)
		st[stot+i]=pt[i],sum[pt[i]]+=v;
	stot+=ptot;	
	Get(st,stot);	
	return ret;
}

struct Node{
	int x,val;	
	Node(int x_=0,int val_=0){
		x=x_;val=val_;
	}
};

bool cmpx(Node x,Node y){
	return sz[x.x]<sz[y.x];
}


Node stack[maxn];
int top;
int Solve(int x){
	int ret=-INF;dis[x]=0;
	int l=top+1,r;
	vis[x]=true;st[stot=1]=x;sum[x]=c[x];
	for(int i=fir[x];i;i=nxt[i])
		if(!vis[to[i]])stack[++top]=Node(to[i],val[i]);
	r=top;
	sort(st+l,st+r+1,cmpx);	
	for(int i=l;i<=r;i++)ret=max(ret,Get_Max(stack[i].x,stack[i].val,c[x]));
	
	for(int i=l;i<=r;i++){
		N=sz[stack[i].x];rt=0;
		Get_RT(stack[i].x,0);
		ret=max(ret,Solve(rt));
	}
	return ret;	
}

int main(){
	freopen("freetourII.in","r",stdin);
	freopen("freetourII.out","w",stdout);
	scanf("%d%d%d",&n,&k,&m);
	while(m--){
		int x;
		scanf("%d",&x);
		c[x]=1;
	}
	for(int i=1,a,b,v;i<n;i++){
		scanf("%d%d%d",&a,&b,&v);
		addedge(a,b,v);
		addedge(b,a,v);
	}
	N=n;rt=0;Get_RT(1,0);
	int ans=Solve(rt);
	printf("%d\n",ans==-INF?0:ans);
	return 0;
}