传送门

不想倍增?数据结构来凑!

答案具有单调性可以二分。

限制了答案后,有一个显然的贪心:在时间允许条件下,一支军队的驻扎点越靠上越优(封锁的点越多)。

那么尽可能把军队往上提。

不搞倍增,直接暴力向上合并。

维护所有位于当前节点的军队以及它们已耗费的时间。

把每个儿子的军队提上来,并给里面的军队时间都加上边权。

然后删掉耗费时间大于当前答案的军队。

于是需要一种支持快速合并、删除大于某个数的元素、整体加的数据结构。

左偏树(可并堆)!

还有一个问题在于根节点不能驻扎。对于根节点不能封锁的儿子,需要将其他儿子剩余的军队移动过来。维护所有需要军队的儿子的边权,和剩余军队的到根节点耗费的时间。双指针扫一遍,把前者较大的和后者较小的匹配检验是否可行。

ちょっと待って。。。好像忽略了一种情况:

(懒得画图了)设需要军队的点为$x$,$y$有一支剩余军队,$z$节点驻扎着一支军队且没有剩余。

可能存在把$z$的军队调往$x$驻扎,$y$的军队调往$z$驻扎满足答案,而直接把$y$的军队调往$x$驻扎不满足的情况。

用已耗费时间衡量军队的优劣的话,这种情况实际上就是把较优的$z$的军队用较劣的$y$的军队“置换”出来。

用$multiset$处理一波,把劣的军队置换出优的军队再检验。还要维护每个点是否有必要驻扎军队,必要的话就把最劣的军队留下。

时间复杂度$O(n\log n\log \sum w)$。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>

#define maxn 50005

const long long inf = 1e18;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
#define ls(x) ls[x]
#define rs(x) rs[x]
long long dat[maxn],tag[maxn],ex[maxn],mid;
int in[maxn],h[maxn],root[maxn],ls[maxn],rs[maxn],siz[maxn],deep[maxn],poi[maxn],ar[maxn],cnt,num;
pair<long long,int>ch[maxn];
multiset<long long>s;
bool ok[maxn],mov[maxn];
struct edge{
    int pre,to,l;
}e[maxn<<1];
inline void add(int from,int to,int l){
    ++in[from];
    e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
}
inline bool cmp(const pair<long long,int> &x,const pair<long long,int>&y){
    if(x.first!=y.first)return x.first>y.first;
    return x.second<y.second;
}
inline void update(int node){
    deep[node]=deep[rs(node)]+1;
    siz[node]=siz[ls(node)]+siz[rs(node)]+1;
}
inline void datadown(int node,int d){
    tag[node]+=d,dat[node]+=d;
}
inline void pushdown(int node){
    if(ls(node))datadown(ls(node),tag[node]);
    if(rs(node))datadown(rs(node),tag[node]);
    tag[node]=0;
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(dat[x]<dat[y])swap(x,y);
    if(tag[x])pushdown(x);
    rs(x)=merge(rs(x),y);
    if(deep[ls(x)]<deep[rs(x)])swap(ls(x),rs(x));
    update(x);
    return x;
}
void push(int &rt,int x){
    dat[++cnt]=x,siz[cnt]=deep[cnt]=1;
    ls(cnt)=rs(cnt)=tag[cnt]=0;
    rt=merge(rt,cnt);
}
void pop(int &rt){
    int l=ls(rt),r=rs(rt);
    if(tag[rt])pushdown(rt);
    rt=merge(l,r);    
}
void dp(int node,int f=1){
    ok[node]=mov[node]=in[node]-1;
    int x,s;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x==f)continue;
        dp(x,node),datadown(root[x],e[i].l);
        root[node]=merge(root[node],root[x]);
        if(root[node]&&dat[root[node]]<=mid)mov[node]=0;
        while(root[node]&&dat[root[node]]>mid)pop(root[node]);
        mov[node]&=ok[x],ok[node]&=ok[x];
    }
    while(root[node]&&dat[root[node]]>mid)pop(root[node]);
    ok[node]|=root[node];
}
inline multiset<long long>::iterator pre(int d){
    multiset<long long>::iterator ans=s.lower_bound(d);
    if(ans==s.end())return --ans;
    if(*ans==d)return ans;
    return --ans;
}
int main(){
    int n=read(),l1,l2,l3,x;
    long long l=0,r=0;
    multiset<long long>::iterator iter;
    for(register int i=1,y,z;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),r+=z;
    int m=read();
    for(register int i=1;i<=m;++i)ar[i]=read();
    if(in[1]>m){puts("-1");return 0;}
    while(l<r){
        mid=l+r>>1,l1=l2=l3=0,cnt=0;
        s.clear(),s.insert(-inf);
        for(register int i=1;i<=n;++i)root[i]=0;
        for(register int i=1;i<=m;++i){
            if(ar[i]==1)ch[++l3]=make_pair(0,0);
            else push(root[ar[i]],0);
        }
        for(register int i=h[1];i;i=e[i].pre){
            x=e[i].to,dp(x);
            if(!ok[x])poi[++l1]=e[i].l;
            if(root[x])ch[++l3]=make_pair(dat[root[x]]+e[i].l,mov[x]?0:e[i].l),pop(root[x]);
            while(root[x])ch[++l3]=make_pair(dat[root[x]]+e[i].l,0),pop(root[x]);
        }
        sort(ch+1,ch+1+l3,cmp);
        for(register int i=1;i<=l3;++i){
            if(!ch[i].second)s.insert(ch[i].first);
            else {
                iter=pre(mid-ch[i].second);
                if(*iter==-inf)continue;
                s.erase(iter);
                s.insert(ch[i].first);
            }
        }
        for(iter=s.begin();iter!=s.end();++iter)ex[++l2]=*iter;
        reverse(ex+1,ex+1+l2),--l2;
        sort(poi+1,poi+1+l1);
        while(l1&&l2&&ex[l2]+poi[l1]<=mid)--l1,--l2;
        if(l1)l=mid+1;
        else r=mid;    
    }
    printf("%lld\n",l);
}