题目链接：Click here
Solution:
直接做看起来很难，我们考虑二分答案之后再来检验
显然，我们事实上只需要在根节点的儿子上都驻扎军队就行了，那么我们就得到了一个贪心策略，将军队尽可能向上提
但是因为根节点不能驻扎军队，所以我们考虑哪些到达根节点还有余力的点该怎么处理
对这些还有余力的点，我们记录下它还能走多少的距离，再按照剩余距离排序
而此时，显然可能还存在一些没有被驻扎的子树，我们把这些子树按照到根节点的距离从大到小排序
对于这些子树，它们有两种选择，由另一颗子树上还能走足够距离的点来驻扎，或者是由本子树上剩余距离最小的来驻扎
如果本子树上的点没有被使用的话，那么我们使用本子树上的点
因为是我们按照剩余距离排序过的，所以若本子树的点没有被使用，则说明它的剩余距离较小，那么它期望带来的价值显然是比当前点要小的，所以我们选择用本子树上的点
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+11;
const int inf=1e9+11;
int n,m,cnt,head[N],vis[N],use[N];
int tot,a[N],dep[N],son[N],f[N][23];
int fmn[N],mark[N],tmp[N];
struct Edge{int nxt,to,val;}edge[N<<1];
struct Army{int res,id;}ar[N];
inline bool cmp(int x,int y){return dep[x]>dep[y];}
inline bool Cmp(Army x,Army y){return x.res>y.res;}
void ins(int x,int y,int z){
edge[++cnt].nxt=head[x];
edge[cnt].to=y;head[x]=cnt;
edge[cnt].val=z;
}
void dfs(int x,int fa){
f[x][0]=fa;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa) continue;
dep[y]=dep[x]+edge[i].val;
dfs(y,x);if(x==1) son[++tot]=y;
}
}
void trans(){
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
int march(int x,int fa){
if(vis[x]) return 1;
int v=0,vv=0;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa) continue;
++v;vv+=march(y,x);
}if(!v) return vis[x];
return v==vv;
}
bool check(int k){
int num1=0,num2=0;
for(int i=1;i<=n;i++) vis[i]=0,use[i]=0,mark[i]=0;
for(int i=1;i<=tot;i++) fmn[son[i]]=inf;
for(int i=1;i<=m;i++){
int x=a[i],y=k;
for(int j=17;j>=0;j--)
if(f[x][j]>1&&y>=dep[x]-dep[f[x][j]])
y-=dep[x]-dep[f[x][j]],x=f[x][j];
if(f[x][0]==1&&y>dep[x]){
ar[++num1].res=y-dep[x],ar[num1].id=i;
if(y<fmn[x]) fmn[x]=y,mark[x]=i;
}else vis[x]=1;
}
sort(ar+1,ar+num1+1,Cmp);
for(int i=1;i<=tot;i++)
if(!march(son[i],1)) tmp[++num2]=son[i];
for(int i=1,now=1;i<=num2;i++){
int x=tmp[i];if(now>num1) return 0;
if(fmn[x]!=inf&&!use[mark[x]]){
use[mark[x]]=1;
continue;
}
while(use[ar[now].id]) ++now;
if(now>num1||ar[now].res<dep[x]) return 0;
use[ar[now].id]=1;
}return 1;
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int x=read(),y=read(),z=read();
ins(x,y,z),ins(y,x,z);
}
dfs(1,0);trans();dep[0]=inf;m=read();
for(int i=1;i<=m;i++) a[i]=read();
sort(son+1,son+tot+1,cmp);
int l=0,r=500000,re=-1;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1,re=mid;
else l=mid+1;
}printf("%lld
",re);
return 0;
}