记录编号	540097	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	LGLJ	是否通过	通过
代码语言	C++	运行时间	3.221 s
提交时间	2019-08-13 16:12:56	内存使用	16.26 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <ctime>
#include <queue>
#include <bitset>
#include <cmath>
#include <deque>
#include <algorithm>
#include <cctype>
#define I inline
#define R register
#define LL long long
#define INF (0x7f7f7f7f)
using namespace std;
struct EDGE
{
	int next,to,val;
}edge[400050]={0};
int head[200050]={0},tot=0;
int k,n,m,mx,all,root,cnt;
int size[200050]={0};
LL dist[200050]={0},ans;
bitset<200050> flag;
bitset<200050> kill;
I int read()
{
	int x=0;
	char ch=0;
	bool w=true;
	while(!isdigit(ch)){if(ch=='-')w=false;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?x:-x;
}
I void add_edge(int u,int v,int val)
{
	edge[++tot].next=head[u];
	edge[tot].to=v;
	edge[tot].val=val;
	head[u]=tot;
}
I void get_root(int u,int fa)
{
	size[u]=1;
	int maxson=0;
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa || kill[v])
			continue;
		get_root(v,u);
		size[u]+=size[v];
		maxson=max(maxson,size[v]);
	}
	maxson=max(maxson,all-size[u]);
	if(maxson<mx)
		mx=maxson,root=u;
}
I int find(int u,int fa)
{
	int sum=0;
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa || kill[v])
			continue;
		sum=max(sum,find(v,u));
	}
	if(flag[u])
		++sum;
	return sum;
}
I void dfs(int u,int fa,int sum,vector<LL> *G)
{
	if(flag[u])
	{
		++sum;
		G[cnt][sum]=max(G[cnt][sum],G[cnt][sum-1]);
	}
	G[cnt][sum]=max(dist[u],G[cnt][sum]);
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa || kill[v])
			continue;
		dist[v]=dist[u]+edge[i].val;
		dfs(v,u,sum,G);
	}
}
I void calc(int u)
{
	dist[u]=0;
	tot=0;
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(kill[v])
			continue;
		++tot;
	}
	vector<LL> G[tot+10];
	pair<int,int> D[tot+10];
	cnt=0;
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(kill[v])
			continue;
		++cnt;
		dist[v]=dist[u]+edge[i].val;
		D[cnt].first=find(v,u);
		D[cnt].second=cnt;
		G[cnt].push_back(-0x3f3f3f3f);
		for(R int j=1;j<=D[cnt].first;++j)
			G[cnt].push_back(-0x3f3f3f3f);
		dfs(v,u,0,G);
	}
	sort(D+1,D+tot+1);
	cnt=k-flag[u];
	for(R int i=1;i<=tot;++i)
	{
		for(R int j=0;j<=min(D[i].first,cnt);++j)
			ans=max(ans,G[D[i].second][j]);
		if(i>=2)
		{
			for(R int j=0;j<=D[i].first;++j)
			{
				int tmp=min(cnt-j,D[i-1].first);
				if(tmp>=0)
					ans=max(ans,G[D[i].second][j]+G[D[i-1].second][tmp]);
			}
			for(R int j=0;j<=D[i-1].first;++j)
				G[D[i].second][j]=max(G[D[i].second][j],G[D[i-1].second][j]);
			for(R int j=1;j<=D[i].first;++j)
				G[D[i].second][j]=max(G[D[i].second][j],G[D[i].second][j-1]);
		}
	}
}
I void query(int u)
{
	kill[u]=true;
	calc(u);
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(kill[v])
			continue;
		mx=all=size[v];
		get_root(v,u);
		query(root);
	}
}
I int MAIN()
{
	freopen ("freetourII.in","r",stdin);
	freopen ("freetourII.out","w",stdout);
	n=read(),k=read(),m=read();
	for(R int i=1,a;i<=m;++i)
	{
		a=read();
		flag[a]=true;
	}
	for(R int i=1,a,b,c;i<n;++i)
	{
		a=read(),b=read(),c=read();
		add_edge(a,b,c);
		add_edge(b,a,c);
	}
	mx=all=n;
	get_root(1,0);
	query(root);
	cout<<ans;
	return 0;
}
int lglj=MAIN();
int main(){;}