#include <stdio.h>
#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <math.h>
#define maxn 50000
using namespace std;
struct node {
int pre , val , to;
} g[maxn << 1 + 5];
struct point {
long long to , val;
};
int m , n , x , y , z , cnt , demaxn , top , ll , rr;
int army[maxn + 5] , st[maxn + 5][35] , fa[maxn + 5] , d[maxn + 5] , dist[maxn + 5][35] , ues[maxn + 5] , v[maxn + 5] , ned[maxn + 5];
bool ok = false , f[maxn + 5] , need[maxn + 5];
long long l = 1 , r , ans;
queue<int> dl;
point remain[maxn + 5];
int cmp(point a , point b) {
return a.val > b.val;
}
void mem() {
memset(f , 0 , sizeof(f));
ll = 0 , rr = 0 , top = 0;
}
int dfs(int rt) {
bool bj = false;
if(f[rt])
return 1;
for(int i = v[rt]; i; i = g[i].pre) {
int p = g[i].to;
if(d[p] < d[rt])
continue;
bj = true;
if(!dfs(p))
return 0;
}
if(!bj)
return 0;
return 1;
}
void add(int ffa , int child , int t) {
g[++cnt].pre = v[ffa];
g[cnt].to = child;
g[cnt].val = t;
v[ffa] = cnt;
}
void RMQ() {
for(int i = 1; i <= m; ++i)
st[i][0] = fa[i];
for(int j = 1; j <= demaxn; ++j) {
for(int i = 2; i + (1 << j) - 1 <= m; ++i) {
st[i][j] = st[st[i][j - 1]][j - 1];
dist[i][j] = dist[st[i][j - 1]][j - 1] + dist[i][j - 1];
}
}
return ;
}
int match() {
if(ll < rr)
return 0;
int i = 1 , j = 1;
while(i <= ll && j <= rr) {
if(ues[i] >= ned[j]) {
++i;
++j;
}
else
++i;
}
if(j > rr)
return 1;
return 0;
}
void back() {
sort(remain + 1 , remain + top + 1 , cmp);
for(int i = 1; i <= top; ++i) {
if(need[remain[i].to] && remain[i].val < dist[remain[i].to][0])
need[remain[i].to] = false;
else
ues[++ll] = remain[i].val;
}
for(int i = v[1]; i; i = g[i].pre)
if(need[g[i].to])
ned[++rr] = g[i].val;
if(rr) sort(ned + 1 , ned + rr + 1);
if(ll) sort(ues + 1 , ues + ll + 1);
}
int cheak(long long ti) {
mem();
long long e , t;
for(int i = 1; i <= n; ++i) {
e = army[i];
t = ti;
for(int j = demaxn; j >= 0; --j) {
if(t - dist[e][j] >= 0 && st[e][j] > 1) {
t -= dist[e][j];
e = st[e][j];
}
}
if(st[e][0] == 1 && t >= dist[e][0]) {
remain[++top].to = e;
remain[top].val = t - dist[e][0];
}
else
f[e] = true;
}
for(int i = v[1]; i; i = g[i].pre)
if(!dfs(g[i].to))
need[g[i].to] = true;
back();
return match();
}
void Binsea() {
long long mid = (l + r) >> 1;
while(l <= r) {
if(cheak(mid)) {
ok = true;
r = mid - 1;
ans = mid;
}
else l = mid + 1;
mid = (l + r) >> 1;
}
}
int main() {
// freopen("P1084_5.in" , "r" , stdin);
// freopen("1084.out" , "w" , stdout);
scanf("%d", &m);
demaxn = log(m) / log(2) + 1;
for(int i = 1; i <= m - 1; ++i) {
scanf("%d %d %d" , &x , &y , &z);
r += z;
add(x , y , z);
add(y , x , z);
}
scanf("%d" , &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &army[i]);
dl.push(1);
d[1] = 1;
int t;
while(dl.size()) {
t = dl.front();
dl.pop();
for(int i = v[t]; i; i = g[i].pre) {
int p = g[i].to;
if(d[p])
continue;
d[p] = d[t] + 1;
fa[p] = t;
dist[p][0] = g[i].val;
dl.push(p);
}
}
RMQ();
Binsea();
if(ok) printf("%d\n" , ans);
else printf("-1");
return 0;
}
希望有大佬帮忙改改,我照着题解打的QAQ