题意太长就不给了
发现答案具有单调性（额外的时间不会对答案造成影响），故考虑二分答案。
贪心地想，在二分了一个时间之后，军队尽量往上走更好。所以我们预处理倍增数组，在二分时间之后通过倍增看某一个军队能到达的深度最低的点。接着，我们发现有一些军队可以到达根节点，还有额外的时间去到别的子树上，而有一些子树没有被封闭完全。这个时候需要我们利用贪心思想来分配军队。
我们将能到达根节点的军队剩余的时间记录下来，并将军队由哪一棵子树而来记录下来，将其按照剩余时间从大到小排序。接着我们处理出没有完全封闭的子树数量，并将它们按照到根节点的边权大小从大到小排序。可以考虑到在分配某一棵子树的时候，一定是在满足条件的情况下选择剩余时间更少的更优。
而满足条件的军队有两种情况：①剩余时间大于等于该子树根节点到根的边权；②原来就由该棵子树来到根节点。对于①情况我们可以直接用指针处理，但是对于②并不是很好处理。我们可以如下处理：对剩余时间不满足条件的军队按照子树来源开个桶，每一次指针移动完毕之后，如果当前子树对应的桶中有军队，就直接拿出这个军队驻守这棵子树，并将这个桶中元素-1，在之后的指针移动中不算在可分配的军队内。
这神题码量真心很长
#include<bits/stdc++.h>
#define MAXN 50010
#define int long long
#define ld long double
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int end , upEd , time;
}Ed[MAXN << ];
struct L{
int ind , lTime;
bool operator < (L a){
return lTime > a.lTime;
}
}now[MAXN];
][] , head[MAXN] , army[MAXN] , N , M , cntEd , cntNow , cntQue;
bool vis[MAXN];
bool cmp(int a , int b){
][] > next[b][][];
}
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].time = c;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void dfs(int now){
; i <= ; i++){
next[now][i][] = next[next[now][i - ][]][i - ][];
next[now][i][] = next[now][i - ][] + next[next[now][i - ][]][i - ][];
}
for(int i = head[now] ; i ; i = Ed[i].upEd){
][]){
next[Ed[i].end][][] = now;
next[Ed[i].end][][] = Ed[i].time;
dfs(Ed[i].end);
}
}
}
inline int jump(int dir , int &k){
; i >= ; i--)
] <= k && next[dir][i][] != ){
k -= next[dir][i][];
dir = next[dir][i][];
}
return dir;
}
queue < int > q;
inline bool bfs(int dir){
while(!q.empty())
q.pop();
vis[dir] = ;
q.push(dir);
while(!q.empty()){
int t = q.front();
q.pop();
)
;
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
q.push(Ed[i].end);
vis[Ed[i].end] = ;
}
}
;
}
inline bool check(int dir){
cntNow = cntQue = ;
memset(vis , , sizeof(vis));
memset(nowDir , , sizeof(nowDir));
vis[] = ;
; i <= M ; i++){
int k = dir , t = jump(army[i] , k);
][] <= k){
now[++cntNow].ind = t;
now[cntNow].lTime = k - next[t][][];
nowDir[t]++;
}
else
vis[t] = ;
}
] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end] && bfs(Ed[i].end))
que[++cntQue] = Ed[i].end;
sort(que + , que + cntQue + , cmp);
sort(now + , now + cntNow + );
, cnt = ;
; i <= cntQue ; i++){
][]){
if(nowDir[now[dik].ind]){
nowDir[now[dik].ind]--;
cnt++;
}
dik++;
}
if(nowDir[que[i]])
nowDir[que[i]]--;
else
if(cnt)
cnt--;
else
;
}
;
}
main(){
next[][][] = ;
N = read();
; i < N ; i++){
int a = read() , b = read() , c = read();
addEd(a , b , c);
addEd(b , a , c);
}
dfs();
M = read();
; i <= M ; i++)
army[i] = read();
, R = 1e14 + ;
while(L < R){
;
if(check(mid))
R = mid;
else
L = mid + ;
}
)
cout << -;
else
cout << L;
;
}