无法有效（不会）直接计算，考虑二分答案
对于一个二分的k
显然尽可能地向上移动军队最优
然而问题并没有这么简单
因为根节点不能覆盖
所以当一棵子树有多支军队，而其他子树没有时
简单地贪心就会出错
需要考虑军队在子树之间的转移
记录所有能在子树间转移的军队的剩余路程和所有需要封锁的子树
在寻找未被封锁的子树时，需要转移的军队并不能参与封锁
从大到小贪心地考虑所有要封锁的子树
- 优先选择已在该子树且剩余距离最小的军队
- 否则选择当前能够使用的军队
细节很多（调了很久）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
118
119
120
121
122
123
124
125
126
127
using namespace std;
const int N=50050,rt=1;
const LL INF=1LL<<50;
struct node{int id;LL val;} A[N],B[N];
int n,f[N],dep[N],v[N],idx,cnt;
int m,w[N],pos[N],used[N];
int log[N],fa[N][20];
LL d[N][20],c[N];
vector<int> e[N],g[N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
bool cmp(node a,node b){return a.val<b.val;}
void add(int u,int v,int val)
{
e[u].push_back(v);
g[u].push_back(val);
}
void update(int k,int o,LL val)
{
for(int i=log[dep[o]];i>=0;i--)
if (d[o][i]<=val&&fa[o][i]>rt)
val-=d[o][i],o=fa[o][i];
c[k]=val-d[o][0],pos[k]=o;
if (!v[o]||c[k]<c[v[o]]) v[o]=k;
f[o]=fa[o][0]==rt?0:1;
}
void calc(int o)
{
if (f[o]) return;
if (e[o].size()==1) return;
int flag=1;
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (dep[to]>dep[o])
{
calc(to);
flag&=f[to];
}
}
f[o]=flag;
}
bool check(LL val)
{
for(int i=1;i<=n;i++) f[i]=v[i]=0;
for(int i=1;i<=m;i++) used[i]=0;
for(int i=1;i<=m;i++) update(i,w[i],val);
calc(rt),idx=cnt=0;
if (f[rt]) return 1;
for(int i=0;i<e[rt].size();i++)
{
int to=e[rt][i];
if (!f[to]) A[++idx]=(node){to,d[to][0]};
}
for(int i=1;i<=m;i++)
if (fa[pos[i]][0]==rt)
B[++cnt]=(node){i,c[i]};
sort(A+1,A+idx+1,cmp);
sort(B+1,B+cnt+1,cmp);
for(int i=idx,j=cnt;i>0;i--)
if (v[A[i].id]&&!used[v[A[i].id]])
used[v[A[i].id]]=1;
else
{
while (used[B[j].id]&&j>0) j--;
used[B[j].id]=1;
if (A[i].val<=B[j].val) j--;else return 0;
}
return 1;
}
void dfs(int o)
{
for(int i=1;i<=log[dep[o]];i++)
{
fa[o][i]=fa[fa[o][i-1]][i-1];
d[o][i]=d[o][i-1]+d[fa[o][i-1]][i-1];
}
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (!dep[to])
{
fa[to][0]=o;
d[to][0]=g[o][i];
dep[to]=dep[o]+1;
dfs(to);
}
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
log[i]=log[i-1]+(1<<log[i-1]==i);
for(int i=1;i<n;i++)
{
int u=read(),v=read();
int val=read();
add(u,v,val);
add(v,u,val);
}
m=read();
for(int i=1;i<=m;i++) w[i]=read();
dep[rt]=1,dfs(rt);
LL L=0,R=INF;
while (L<R)
{
LL mid=(L+R)>>1;
if (check(mid))
R=mid;
else
L=mid+1;
}
printf("%lld\n",R==INF?-1:R);
return 0;
}