记录编号	358295	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	9.400 s
提交时间	2016-12-15 15:35:30	内存使用	9.38 MiB

#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 2e9;


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0, flag = 1;
	
	while (not is_num(tmp)) {
		if (tmp == '-') flag = -1;
		tmp = getchar();
	}
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res * flag;
}


struct Node {
	int dis, num;
	Node() {}
	Node(int dis_, int num_) { dis = dis_, num = num_; }
	
	bool operator < (const Node &b) const { return num == b.num ? dis < b.dis : num < b.num; }
};


struct NextNode {
	int to, sz, v;
	NextNode() {}
	NextNode(int to_, int sz_, int v_) { to = to_, sz = sz_, v = v_; }
	
	bool operator < (const NextNode &b) const { return sz < b.sz; } 
} nn[MAXN];


struct Edge {
	int to, ne, v;
	Edge() {}
	Edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
} e[MAXN << 1];
int head[MAXN], ecnt;
inline void add_edge(int fr, int to, int v) {
	e[++ecnt] = Edge(to, head[fr], v), head[fr] = ecnt;
	e[++ecnt] = Edge(fr, head[to], v), head[to] = ecnt;
}


bool del[MAXN];
bool nava[MAXN];
int cost[MAXN];
int sz[MAXN];
int tot_sz, ne_root;
int global_ans;
int n, m, k;


void cal_root(int now, int fa) {
	sz[now] = 1;
	int tmp_mx = 0;
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa or del[to]) continue;
		
		cal_root(to, now);
		if (sz[tmp_mx] < sz[to]) tmp_mx = to;
		sz[now] += sz[to];
	}
	
	cost[now] = max(sz[tmp_mx], tot_sz - sz[now]);
	if (cost[now] < cost[ne_root]) ne_root = now;
}


void cal_path(int now, int fa, set <Node> &now_dis, int dis, int num) {
	set <Node> :: iterator it;
	it = now_dis.upper_bound(Node(INF, k - num));
	if (it != now_dis.begin()) {
		it--;
		if ((*it).num + num <= k) global_ans = max(global_ans, dis + (*it).dis);
	}
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa or del[to]) continue;
		
		cal_path(to, now, now_dis, dis + e[i].v, num + nava[to]);
	}
}


void add_path(int now, int fa, set <Node> &now_dis, int dis, int num) {
	set <Node> :: iterator it;
	it = now_dis.lower_bound(Node(-INF, num));
	if (it != now_dis.end()) {
		if ((*it).num == num) {
			if ((*it).dis < dis) {
				now_dis.erase(it);
				now_dis.insert(Node(dis, num));
			}
		} else now_dis.insert(Node(dis, num));
	} else now_dis.insert(Node(dis, num));
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa or del[to]) continue;
		
		add_path(to, now, now_dis, dis + e[i].v, num + nava[to]);
	}
}


inline void out(set <Node> &now_dis) {
	set <Node> :: iterator it;
	for (it = now_dis.begin(); it != now_dis.end(); it++) {
		printf("num = %d dis = %d\n", (*it).num, (*it).dis);
	}
}


inline void adjust(set <Node> &now_dis) {
	set <Node> :: iterator it = now_dis.begin();
	int now_max = -INF;
	Node tmp, del;
	while (it != now_dis.end()) {
		// printf("sz = %d %d %d\n", now_dis.size(), (*it).num, (*it).dis);
		if ((*it).num <= k) global_ans = max(global_ans, (*it).dis);
		if ((*it).dis >= now_max) {
			now_max = ((*it).dis);
			it++;
			continue;
		}
		tmp = Node(now_max, (*it).num);
		del = (*it);
		it++;
		now_dis.erase(del);
		now_dis.insert(tmp);
	}
}


void tree_div(int now) {
	// printf("now = %d\n", now);
	set <Node> now_dis;
	now_dis.clear();
	del[now] = true;
	
	int nncnt = 0;
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (del[to]) continue;
		
		nn[++nncnt] = NextNode(to, sz[to], e[i].v); // 懒省事.. 就这么写吧 - - 
	}
	
	sort(nn + 1, nn + nncnt + 1);
	for (int i = 1; i <= nncnt; i++) {
		int to = nn[i].to;
		if (del[to]) continue;
		
		// if (sz[to] >= 2) printf("%d\n", to);
		cal_path(to, now, now_dis, nn[i].v, nava[to]);
		// printf("cal done\n");
		add_path(to, now, now_dis, nn[i].v, nava[now] + nava[to]);
		// printf("add done\n");
		// out(now_dis);
		adjust(now_dis);
		// printf("adj done\n");
		
		// printf("now %d son %d:\n", now, to);
		// out(now_dis);
	}

	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (del[to]) continue;
		
		tot_sz = sz[to];
		ne_root = 0;
		cal_root(to, now);
		// printf("ne root = %d\n", ne_root);
		tree_div(ne_root);
	}
}


inline void read() {
	n = get_num(), k = get_num(), m = get_num();
	int tmp, fr, to, v;
	for (int i = 1; i <= m; i++) {
		tmp = get_num();
		nava[tmp] = true;
	}
	for (int i = 1; i <= n - 1; i++) {
		fr = get_num(), to = get_num(), v = get_num();
		add_edge(fr, to, v);
	}
} 


inline void solve() {
	sz[0] = 0;
	cost[0] = INF;
	global_ans = 0;
	
	tot_sz = n;
	ne_root = 0;
	cal_root(1, 0);
	tree_div(ne_root);
	
	printf("%d\n", global_ans);
}


int main() {
	freopen("freetourII.in", "r", stdin);
	freopen("freetourII.out", "w", stdout);
	read();
	solve();
	return 0;
}