记录编号	226679	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1825] 免费旅行II	最终得分	100
用户昵称	stone	是否通过	通过
代码语言	C++	运行时间	9.458 s
提交时间	2016-02-18 10:31:51	内存使用	13.67 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200000 + 5;
const int inf = 1e9;

int ans = -inf;
int n, k, m, sum, max_size, cnt;
int head[N], depth[N], fa[N], d[N];
int size[N], que[N], c[N], tmp[N<<1];
int tmp_cnt = 0;
bool vi[N], flag[N];

struct Edge {
  int from, to, dis, next;
}edges[N<<1];

void insert(int from, int to, int dis) {
  ++ cnt;
  edges[cnt].from = from;
  edges[cnt].to = to;
  edges[cnt].dis = dis;
  edges[cnt].next = head[from];
  head[from] = cnt;
}

void change(int pos) {
  for(int i = pos; i <= k + 2; i += (i & (-i))) {
	c[i] = -inf;
  }
}
int query(int x) {
  int res = -inf;

  for(int i = x; i > 0; i -= (i & (-i))) {
	res = max(res, c[i]);
  }
  return res;
}

void update(int pos, int val) {
  for(int i = pos; i <= k + 2; i += (i & (-i))) {
	c[i] = max(c[i], val);
  }
}

void getg(int u, int f, int &rt) {
  int maxx = 0;

  size[u] = 1;
  for(int i = head[u]; i; i = edges[i].next) {
	int v = edges[i].to;

	if(!vi[v] && v != f) {
	  getg(v, u, rt);
	  size[u] += size[v];
	  maxx = max(size[v], maxx);
	}
  }
  maxx = max(sum - maxx, maxx);
  if(maxx < max_size) {
	max_size = maxx;
	rt = u;
  }
}

void calc(int u) {
  for(int i = head[u]; i; i = edges[i].next) {
	int v = edges[i].to;

	if(vi[v]) continue;

	int h = 1, t = 1;

	que[h] = v; fa[v] = u;
	d[v] = edges[i].dis;
	depth[v] = flag[v];
	while(h <= t) {
	  int x = que[h];

	  for(int j = head[x]; j; j = edges[j].next) {
		int to = edges[j].to;

		if(!vi[to] && to != fa[x]) {
		  fa[to] = x;
		  d[to] = d[x] + edges[j].dis;
		  depth[to] = depth[x] + flag[to];
		  que[++ t] = to;
		}
	  }
	  ++ h;
	}
	for(int j = 1; j <= t; ++ j) {
	  int x = que[j];

	  if(depth[x] <= k) {
		int lmd = query(k - depth[x] + 1);

		ans = max(d[x] + lmd, ans);
		ans = max(ans, d[x]);
	  }
	}
	for(int j = 1; j <= t; ++ j) {
	  int x = que[j];

	  if(depth[x] <= k) {
		update(depth[x] + 1, d[x]);
		tmp[++ tmp_cnt] = depth[x] + 1;
	  }
	}
  }
  for(int i = 1; i <= tmp_cnt; ++ i)
	change(tmp[i]);
  tmp_cnt = 0;
}

void solve(int u) {
  int rt;

  max_size = n + 1;
  getg(u, 0, rt);
  u = rt;
  if(flag[u]) k --;
  calc(u);
  if(flag[u]) k ++;
  vi[u] = true;
  for(int i = head[u]; i; i = edges[i].next) {
	int v = edges[i].to;

	if(!vi[v]) {
	  sum = size[v];
	  solve(v);
	}
  }
}

int qread() {
  int x = 0; char ch = getchar();

  while(ch > '9' || ch < '0') ch = getchar();
  while(ch <= '9' && ch >= '0') {
	x = x * 10 + ch - '0';
	ch = getchar();
  }
  return x;
}

int main() {
  int __size__ = 64 << 20;
  char *__p__ = (char*)malloc(__size__) + __size__;
  __asm__("movl %0, %%esp\n" :: "r"(__p__));

#ifndef ONLINE_JUDGE
  freopen("freetourII.in", "r", stdin);
  freopen("freetourII.out", "w", stdout);
#endif
  
  int u, v, w;
  
  n = qread(); k = qread(); m = qread();
  for(int i = 1; i <= m; ++ i) {
	scanf("%d", &u);
	flag[u] = true;
  }
  for(int i = 1; i < n; ++ i) {
	u = qread(); v = qread();
	scanf("%d", &w);
	insert(u, v, w); insert(v, u, w);
  }
  for(int i = 1; i <= k + 1; ++ i)
	c[i] = -inf;
  sum = n;
  solve(1);
  printf("%d\n", ans == -inf ? 0 : ans);
#ifndef ONLINE_JUDGE
  fclose(stdin); fclose(stdout);
#endif
  return 0;
}