RT，WA $70 \operatorname{pts}$，死在了 #4 #5 #7 /kk

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

typedef long long ll;

typedef struct {
	int nxt;
	int end;
	int dis;
} Edge;

typedef struct {
	ll rest;
	int top;
} Army;

int cnt = 0;
int head[50007], depth[50007], fa[50007][27], city[50007];
ll dis[50007][27];
bool vis1[50007], vis2[50007];
Edge edge[100007];
Army army[50007];
priority_queue<int> q;

inline void add_edge(int start, int end, int dis){
	cnt++;
	edge[cnt].nxt = head[start];
	head[start] = cnt;
	edge[cnt].end = end;
	edge[cnt].dis = dis;
}

void dfs1(int u, int father){
	int t;
	depth[u] = depth[father] + 1;
	t = log2(depth[u]) + 1;
	fa[u][0] = father;
	vis1[u] = true;
	for (register int i = 1; i <= t; i++){
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		dis[u][i] = dis[u][i - 1] + dis[fa[u][i - 1]][i - 1];
	}
	for (register int i = head[u]; i != 0; i = edge[i].nxt){
		int x = edge[i].end;
		if (x != father){
			dis[x][0] = edge[i].dis;
			vis1[u] = false;
			dfs1(x, u);
		}
	}
}

bool cmp1(const Army a, const Army b){
	if (a.rest != b.rest) return a.rest < b.rest;
	return a.top < b.top;
}

bool dfs2(int u, int father){
	if (vis1[u]) return true;
	for (register int i = head[u]; i != 0; i = edge[i].nxt){
		int x = edge[i].end;
		if (x != father && !vis2[x] && dfs2(x, u)) return true;
	}
	return false;
}

bool cmp2(const Army a, const Army b){
	if (a.rest != b.rest) return a.rest > b.rest;
	return a.top < b.top;
}

inline bool check(int n, int m, ll k){
	int cnt = 0;
	for (register int i = 1; i <= n; i++){
		vis2[i] = false;
	}
	for (register int i = 1; i <= m; i++){
		int cur = city[i];
		ll rest = k;
		for (register int j = log2(depth[cur]) + 1; j >= 0; j--){
			if (fa[cur][j] > 1 && rest >= dis[cur][j]){
				rest -= dis[cur][j];
				cur = fa[cur][j];
			}
		}
		if (fa[cur][0] == 1 && rest >= dis[cur][0]){
			cnt++;
			army[cnt].rest = rest - dis[cur][0];
			army[cnt].top = cur;
		} else {
			vis2[cur] = true;
		}
	}
	sort(army + 1, army + cnt + 1, cmp1);
	for (register int i = 1; i <= cnt; i++){
		if (!vis2[army[i].top] && army[i].rest < dis[army[i].top][0] && dfs2(army[i].top, 1)){
			vis2[army[i].top] = true;
			army[i].rest = -1;
		}
	}
	sort(army + 1, army + cnt + 1, cmp2);
	for (register int i = head[1]; i != 0; i = edge[i].nxt){
		int x = edge[i].end;
		if (!vis2[x] && dfs2(x, 1)) q.push(edge[i].dis);
	}
	for (register int i = 1; !q.empty(); i++){
		if (army[i].rest < q.top()){
			while (!q.empty()) q.pop();
			return false;
		}
		q.pop();
	}
	return true;
}

int main(){
	int n, m;
	ll l = 0, r = 0, ans;
	cin >> n;
	for (register int i = 1; i < n; i++){
		int u, v, w;
		cin >> u >> v >> w;
		r += w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	dfs1(1, 0);
	cin >> m;
	for (register int i = 1; i <= m; i++){
		cin >> city[i];
	}
	for (register int i = head[1], j = 1; i != 0; i = edge[i].nxt, j++){
		if (j > m){
			cout << -1;
			return 0;
		}
	}
	while (l <= r){
		ll mid = (l + r) >> 1;
		if (check(n, m, mid)){
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
	return 0;
}