1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using std::sort;
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(5e5 + 10);
struct edge { int next, to, dis; } e[maxn << 1];
struct node { long long val; int id; } a[maxn], b[maxn];
int head[maxn], e_num, n, m, pos[maxn], cnta, cntb;
inline bool cmp(const node &lhs, const node &rhs) { return lhs.val < rhs.val; }
inline void add_edge(int from, int to, int dis)
{
e[++e_num] = (edge) {head[from], to, dis}; head[from] = e_num;
e[++e_num] = (edge) {head[to], from, dis}; head[to] = e_num;
}
int dep[maxn], f[maxn][22], dis[maxn][22], vis[maxn];
void dfs(int x)
{
for(RG int i = 1; i <= 20 && f[f[x][i - 1]][i - 1]; i++)
f[x][i] = f[f[x][i - 1]][i - 1], dis[x][i] = dis[f[x][i - 1]][i - 1] + dis[x][i - 1];
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == f[x][0]) continue;
dep[to] = dep[x] + 1; f[to][0] = x; dis[to][0] = e[i].dis; dfs(to);
}
}
void pushdown(int x)
{
bool a = 1, b = 0;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == f[x][0]) continue;
pushdown(to); a &= vis[to]; b = 1;
}
if(x != 1 && a && b) vis[x] = 1;
}
inline bool check(int mid)
{
cnta = cntb = 0; clear(vis, 0);
for(RG int i = 1; i <= m; i++)
{
int x = pos[i], t = 0;
for(RG int j = 20; ~j; j--) if(f[x][j] && t + dis[x][j] <= mid) t += dis[x][j], x = f[x][j];
if(x != 1) vis[x] = 1;
else
{
x = pos[i]; a[++cnta].val = mid - t;
for(RG int j = 20; ~j; j--) if(f[x][j] > 1) x = f[x][j];
a[cnta].id = x;
}
}
pushdown(1);
for(RG int i = head[1]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to]) continue;
b[++cntb] = (node) {e[i].dis, to};
}
sort(a + 1, a + cnta + 1, cmp);
sort(b + 1, b + cntb + 1, cmp);
RG int p = 1;
for(RG int i = 1; i <= cnta; i++)
{
if(!vis[a[i].id]) vis[a[i].id] = 1;
else if(a[i].val >= b[p].val) vis[b[p].id] = 1;
while(vis[b[p].id] && p <= cntb) ++p;
}
return cntb < p;
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(); int sum = 0;
for(RG int i = 1, a, b, c; i < n; i++)
a = read(), b = read(), sum += (c = read()), add_edge(a, b, c);
dep[1] = 1; dfs(1); m = read();
for(RG int i = 1; i <= m; i++) pos[i] = read();
int l = 0, r = sum, ans; sum = 0;
for(RG int i = 1; i <= n; i++) sum += (dep[i] == 2);
if(m < sum) return puts("-1") & 0;
while(l <= r)
{
int mid = (l + r) >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
|