首先,所有军队又要尽量往上走,这样才能尽可能的封锁更多的到叶子的路径
而随着时间的增加,能封锁的路径也就越来越多,所以可以二分最终的时间
然后对于每个时间,就让能走到根的军队走到根,记录到根上一个节点和剩余时间,然后按时间排序;不能走到的就在能走到的最上面的点打标记.然后遍历树一遍,把所有的儿子被打标记的点打标记;然后把根的没打标记的儿子提出来,和之前到达根的军队一一匹配:把那些儿子按照到根的距离从大到小排序,对于每个儿子,考虑用退回上一个节点匹配,不行就用剩余时间足够的匹配,都不行就用当前军队退回去匹配,然后考虑下一个军队
有点毒瘤似不似
注:保存到根的节点建议用(multiset),向下面代码里面写的能过洛谷上的题,但是仍有问题懒得改了
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define inf 2099999999
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define db double
#define eps (1e-5)
using namespace std;
const int N=50000+10;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
LL w[N<<1];
il void add(int x,int y,LL z)
{
++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;
}
struct nnn
{
LL x;int la;
bool operator < (const nnn &a) const{return x>a.x;}
}st[N<<1];
int n,m,nn,a[N],fa[N][17],tt,tp,cn[N];
LL s[N][17],di[N],l,r,ans,so[N];
bool v[N];
il bool cmp(int a,int b){return di[a]>di[b];}
void dfs(int x)
{
r=max(r,di[x]);
for(int j=1;j<=nn;j++) fa[x][j]=fa[fa[x][j-1]][j-1],s[x][j]=(fa[x][j]>0)?(s[x][j-1]+s[fa[x][j-1]][j-1]):(1ll<<50);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x][0]) continue;
fa[y][0]=x,s[y][0]=w[i],di[y]=di[x]+w[i];
dfs(y);
}
}
void dd(int x)
{
if(v[x]) return;
v[x]=true;
int cnt=0;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x][0]) continue;
dd(y);
v[x]&=v[y];
++cnt;
}
if(!cnt) v[x]=false;
}
il bool check(LL ti)
{
memset(v,0,sizeof(v));
memset(cn,0,sizeof(cn));
tt=tp=0;
for(int i=1;i<=m;i++)
{
if(di[a[i]]<ti)
{
int nw=a[i];
for(int j=nn;j>=0;j--) if(fa[nw][j]>1) nw=fa[nw][j];
st[++tt]=(nnn){ti-di[a[i]],nw},++cn[nw];
continue;
}
int nw=a[i];LL ss=0;
for(int j=nn;j>=0;j--) if(ss+s[nw][j]<=ti&&fa[nw][j]>1) ss+=s[nw][j],nw=fa[nw][j];
if(nw>1) v[nw]=true;
}
sort(st+1,st+tt+1);
dd(1);
for(int i=hd[1];i;i=nt[i])
if(!v[to[i]]) so[++tp]=to[i];
sort(so+1,so+tp+1,cmp);
int j=1;
for(int i=1;i<=tt&&j<=tp;i++)
{
if(cn[so[j]]>0) --cn[so[j]],--i,v[so[j]]=true;
else if(st[i].x>=di[so[j]]&&cn[st[i].la]>0) --cn[st[i].la],v[so[j]]=true;
else if(cn[st[i].la]>0) --cn[st[i].la],st[++tt]=(nnn){st[i].x,st[i].la},v[st[i].la]=true;
while(j<=tp&&v[so[j]]==true) ++j;
}
return j>tp;
}
int main()
{
n=rd(),nn=log(n)/log(2)+1;
for(int i=1;i<n;i++)
{
int x=rd(),y=rd(),z=rd();
add(x,y,z);
}
dfs(1);
m=rd();
for(int i=1;i<=m;i++) a[i]=rd();
l=0,r<<=1ll,ans=1ll<<60;
while(l<=r)
{
LL mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld
",ans<(1ll<<60)?ans:-1);
return 0;
}