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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
struct Edge {
	int next, to, dis;
	Edge(int a=0, int b=0, int c=0) :
		next(a), to(b), dis(c) {}
} e[maxn<<1];
int head[maxn], tot;
void Add(int u, int v, int w) {
	e[++tot] = Edge(head[u], v, w); head[u] = tot;
}
int N, K, M, size[maxn], F, Size, root;
bool bk[maxn], vis[maxn];
int dep[maxn], Dep, son;
Edge t[maxn];
void getD(int x, int fa, int b, int &D) {
	D = max(b, D);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		getD(to, x, b+bk[to], D);
	}
}
void getdep(int x, int fa, int b, int d, int &ans, bool BK) {
	if(b+BK>K) return; //warn
	ans = max(ans, d+dep[min(K-b-BK, Dep)]);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		getdep(to, x, b+bk[to], d+e[i].dis, ans, BK);
	}
} 
void givediff(int x, int fa, int b, int d) {
	dep[b] = max(dep[b], d);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		givediff(to, x, b+bk[to], d+e[i].dis);
	}
}
bool cmp(const Edge &x, const Edge &y) { return x.next < y.next; }
void calc(int x, int &ans) {
	Dep = son = 0; dep[0] = 0;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		t[++son] = Edge(0, to, e[i].dis);
		getD(to, x, bk[to], t[son].next); 
	} 
	sort(t+1, t+son+1, cmp); 
	for(int i=1; i<=son; ++i) { 
		int to = t[i].to; 
		getdep(to, x, bk[to], t[i].dis, ans, bk[x]); 
		givediff(to, x, bk[to], t[i].dis); 
		Dep = max(Dep, t[i].next);
		for(int j=1; j<=Dep; ++j) 
			dep[j] = max(dep[j], dep[j-1]);
	} 
	for(int i=0; i<=Dep; ++i) dep[i] = 0; 
} 
int getroot(int x, int fa) {
	int f = 0; size[x] = 1;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		size[x] += getroot(to, x);
		f = max(f, size[to]);
	}
	f = max(f, Size-size[x]);
	if(f<=F) F = f, root = x;
	return size[x];
}
int solve(int x, int &ans) {
	vis[x] = 1; calc(x, ans);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		F = Size = size[to]; getroot(to, x);
		solve(root, ans);
	}
	return ans;
}
int main() {
	freopen("freetourII.in","r",stdin);
	freopen("freetourII.out","w",stdout);
	scanf("%d%d%d", &N, &K, &M);
	for(int i=1,a; i<=M; ++i) 
		scanf("%d", &a), bk[a] = 1;
	for(int i=1,a,b,c; i<N; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		Add(a, b, c); Add(b, a, c);
	}
	F = Size = N; getroot(1, 0);
	int ans = 0; solve(root, ans);
	printf("%d\n", ans);
	getchar(), getchar();
	return 0;
}