记录编号	236483	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	10.453 s
提交时间	2016-03-14 14:15:04	内存使用	9.94 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int cc[200010],n,m,k,w[200010];
int z[200010];
bool b[200010],bc[200010];
int crowd[200010],q[200010];
bool B[200010];
int MA,pr,ll;
inline int gl(int a)
{
	return a&(-a);
}
inline void gj(int a,int z)
{
	while(a<=k+5)
	{
		if(cc[a]<z)
		{
		    cc[a]=z;
		    if(!B[a])
		    {
		    	q[++ll]=a;
		    	B[a]=1;
		    }
		}
		a+=gl(a);
	}
}
inline int gs(int a)
{
	int u=-0x3fffffff;
	while(a>0)
	{
		if(u<cc[a])
		    u=cc[a];
		a-=gl(a);
	}
	return u;
}
struct u
{
	int b;
	int x;
	int z;
}c[400010];
int f[200010];
int h[200000];
int l,rt,sum;
bool Crowd;
inline void gjj(int a,int b,int z)
{
	c[++l].b=b;
	c[l].x=h[a];
	c[l].z=z;
	h[a]=l;
	return;
}
int getroot(int a,int fa)
{
	int p=0;
	w[a]=1;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(b[u]||u==fa)
		    continue;
		getroot(u,a);
		w[a]+=w[u];
		if(p<w[u])
		    p=w[u];
	}
	if(p<sum-w[a])
	    p=sum-w[a];
	if(p<MA)
	{
		MA=p;
		rt=a;
	}
}
void gw(int a,int rt)
{
	if(crowd[a]>k)
	    return;
	f[a]=z[a];
	int o=gs(k-crowd[a]+Crowd+1);
	if(f[a]<z[a]+o)
	    f[a]=z[a]+o;
	if(f[a]>pr)
	    pr=f[a];
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(u==rt||b[u])
		    continue;
		z[u]=z[a]+c[i].z;
		crowd[u]=crowd[a]+bc[u];
		gw(u,a);
	}
	return;
}
void gin(int a,int rt)
{
	if(crowd[a]>k)
	    return;
	gj(crowd[a]+1,z[a]);
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(u==rt||b[u])
		    continue;
		gin(u,a);
	}
	return;
}
void g(int a,int fa)
{
	//printf("%d\n",a);
	b[a]=1;
	z[a]=0;
	crowd[a]=bc[a];
	Crowd=bc[a];
	while(ll)
	{
		cc[q[ll]]=-0x3fffffff;
		B[q[ll]]=0;
		--ll;
	}
	if(h[a]==-1)
	    return;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(u==fa||b[u])
		    continue;
		z[u]=z[a]+c[i].z;
		crowd[u]=crowd[a]+bc[u];
		gw(u,a);
		gin(u,a);
	}
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(u==fa||b[u])
		    continue;
		MA=0x3fffffff;
		sum=w[u];
		getroot(u,0);
		g(rt,a);
	}
}
int main()
{
	int __size__ = 30 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	freopen("freetourII.in","r",stdin);
	freopen("freetourII.out","w",stdout);
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;i++)
	{
		int aa;
		scanf("%d",&aa);
		bc[aa]=1;
	}
	for(int i=1;i<n;i++)
	{
		int aa,bb,cc;
		scanf("%d%d%d",&aa,&bb,&cc);
		gjj(aa,bb,cc);
		gjj(bb,aa,cc);
	}
	memset(cc,-0x3f,sizeof(cc));
	MA=0x7fffffff;
	sum=n;
	getroot(1,0);
	g(rt,0);
	printf("%d",pr);
	getchar();
	getchar();
}