因为若一个时间限制满足题意，则所有比它大的时间限制一定都满足题意，因此本题答案具有单调性，可以想到二分答案求解。本题思路不是很难，但细节和代码实现比较复杂。
```cpp
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=6e4;
int n,m,t,tot,atot,btot,ctot;
int d[N],query[N],f[N][20];
int to[N<<1],edge[N<<1],nxt[N<<1],head[N];
bool ok,sta[N],need[N];
ll ans,tim[N],ned[N],dist[N][20];
pair<ll,int> h[N];
queue<int> q;
void add(int x,int y,int z){
nxt[++tot]=head[x];head[x]=tot;to[tot]=y;edge[tot]=z;
}
void bfs(){
q.push(1);d[1]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;dist[y][0]=edge[i];
for(int j=1;j<=t;j++){
f[y][j]=f[f[y][j-1]][j-1];
dist[y][j]=dist[y][j-1]+dist[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
void init(){
memset(sta,0,sizeof(sta));
memset(tim,0,sizeof(tim));
memset(ned,0,sizeof(ned));
memset(h,0,sizeof(h));
memset(need,0,sizeof(need));
atot=0,btot=0,ctot=0;
}
bool dfs(int x){
bool pson=0;
if(sta[x]) return 1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(d[y]<d[x]) continue;
pson=1;
if(!dfs(y)) return 0;
}
if(!pson) return 0;
return 1;
}//如果是叶子结点，pson=0，那么该路径没有军队驻扎
bool ck(ll lim){
for(int i=1;i<=m;i++){//上移军队并处理闲置军队
ll x=query[i],cnt=0;
for(int j=t;j>=0;j--)
if(f[x][j]>1/*不能是根节点*/ && cnt+dist[x][j]<=lim){
cnt+=dist[x][j];
x=f[x][j];
}
if(f[x][0]==1 && cnt+dist[x][0]<=lim)
h[++ctot]=make_pair(lim-cnt-dist[x][0],x);
else sta[x]=1;
}
for(int i=head[1];i;i=nxt[i])
if(!dfs(to[i])) need[to[i]]=1;//dfs寻找路径未被驻扎的叶子节点
sort(h+1,h+ctot+1);//第一关键字排序
for(int i=1;i<=ctot;i++)
if(need[h[i].second] && h[i].first<dist[h[i].second][0])
need[h[i].second]=0;
else tim[++atot]=h[i].first;//对根节点的需要被驻扎的子节点进行初步处理
for(int i=head[1];i;i=nxt[i])
if(need[to[i]]) ned[++btot]=dist[to[i]][0];//找到仍需要被驻扎的节点并存储
if(atot<btot) return 0;//无解
sort(ned+1,ned+btot+1);
int i=1,j=1;
while(i<=btot && j<=atot)//双指针扫描
if(tim[j]>=ned[i]) i++,j++;
else j++;
if(i>btot) return 1;
return 0;
}
int main(){
cin>>n;ll l=0,r=0,mid;
t=log2(n)+1;
for(int i=1;i<n;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);r+=z;
}
bfs();//树上倍增预处理
cin>>m;for(int i=1;i<=m;i++) scanf("%d",&query[i]);//存每个军队
while(l<=r){//二分答案
init();mid=(l+r)>>1;
if(ck(mid)) r=mid-1,ans=mid,ok=1;
else l=mid+1;
}
if(!ok) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
```
by chaizechen_czc @ 2023-08-27 21:07:27