Description：

给一棵树，每条边有通过时间，在一些节点上已经驻扎有军队，军队可以封锁一个节点，也可以在边上移动，问最少可以用多长时间使得从一号节点无法到达叶子节点。

$1\le n \le 50000$

Solution：

如果 $t$ 时间可以，那么 $>t$ 的时间都可以，所以可以二分这个 $t$ ，在给定的时间内，军队驻扎的位置肯定是越靠上越好，分两种情况，一是跳不到根节点的，那就让他驻扎在他能到的最高点上，如果跳到最高点，那么我们把这个点记下来，发现这些点可以越过根节点，他们一定是越过根节点后封锁了根节点的一个子节点，于是把根节点的所有子节点用一个 $vector$ 记下来，然后二分，这里二分的边界我设的是最大深度的二倍，然后就让每个点往上跳，显然不能一个一个跳，要倍增跳，跳的时候还要注意不能恰好到达根节点，然后把没跳到根节点的军队最终的位置打上封锁标记，然后再 $dfs$ 这棵树，判断根节点的每个子节点是否已经封锁，如果他的所有子节点都被封锁了，那他也没用了，注意根的特殊性，然后把每个跳过根的军队表示为一个 $pair$ ，分别记录它跳过根后还能走多远和它来自哪棵子树，每个根节点的子节点也做成一个 $pair$ ，分别记录深度和编号，然后把这两个都按距离从小到大排序，然后维护双指针，如果当前这个军队来自的子树还没有被封锁，那他就封锁这个子节点，因为它是最小的，所以他自己封锁一定最优，否则找另一个距离最小的封锁，因为反正这个子树迟早要封锁，所以不如现在就封上以后一定不会更劣，注意找最小时可能会跳过很多已经封锁的子树，最后判断根节点的所有子节点是否都被封死。

无解就是军队数 $<$ 子节点数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

struct edge

{

    int to,nxt,w;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].w = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].w = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

int f[MAXN][17];

int dep[MAXN],fa[MAXN];

bool vis[MAXN];

bool tag[MAXN];

void dfs(int k,int depth)

{

    dep[k] = depth;vis[k] = true;

    tag[k] = true;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(vis[e[i].to])continue;

        tag[k] = false;

        fa[e[i].to] = k;f[e[i].to][0] = k;

        dfs(e[i].to,depth + e[i].w);

    }

    return;

}

vector< pair<int,int> > v;

int pos[MAXN];

bool hold[MAXN];

struct army{int subtree,dis;};

army s[MAXN];

#define fi first

#define se second

int top;

bool lock[MAXN];

void mark(int k)

{

    vis[k] = true;

    if(hold[k])

    {

        lock[k] = true;

        return;

    }

    if(tag[k])return;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(vis[e[i].to])continue;

        mark(e[i].to);

        if(k != 1 && !lock[e[i].to])return;

    }

    lock[k] = true;

    return;

}

bool cmp_army_from_low_to_high(army x,army y){return x.dis < y.dis;}

bool check(int k)

{

    top = 0;

    memset(hold,false,sizeof(hold));

    for(int i = 1;i <= m;++i)

    {

        if(dep[pos[i]] >= k)

        {

            int t = k;if(dep[pos[i]] == k)--t;

            int p = pos[i];

            for(int w = 16;w >= 0;--w)

                if(dep[pos[i]] - dep[f[p][w]] <= t)

                    p = f[p][w];

            hold[p] = true;

        }

        else

        {

            int p = pos[i];

            for(int w = 16;w >= 0;--w)

                if(dep[f[p][w]] != 0)

                    p = f[p][w];

            s[++top] = (army){p,k - dep[pos[i]]};

        }

    }

    sort(s + 1,s + 1 + top,cmp_army_from_low_to_high);

    sort(v.begin(),v.end());

    memset(lock,false,sizeof(lock));

    memset(vis,false,sizeof(vis));

    mark(1);

    for(int i = 1,j = 0;i <= top && j < v.size();++i)

    {

        while(j < v.size() && lock[v[j].se])++j;

        if(j == v.size())break;

        if(!lock[s[i].subtree])

        {

            lock[s[i].subtree] = true;

            continue;

        }

        else

        {

            if(s[i].dis >= v[j].fi)

            {

                lock[v[j].se] = true;

                ++j;

            }

        }

    }

    for(int i = 0;i < v.size();++i)

    {

        if(!lock[v[i].se])return false;

    }

    return true;

}

int main()

{

    scanf("%d",&n);

    int a,b,c;

    for(int i = 1;i < n;++i)

    {

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

    }

    dfs(1,0);

    for(int i = 1;i <= 16;++i)

        for(int k = 1;k <= n;++k)

            f[k][i] = f[f[k][i - 1]][i - 1];

    scanf("%d",&m);

    memset(pos,0,sizeof(pos));

    for(int i = 1;i <= m;++i)

    {

        scanf("%d",&pos[i]);

    }

    for(int i = lin[1];i != 0;i = e[i].nxt)v.push_back(make_pair(e[i].w,e[i].to));

    if(m < v.size())

    {

        puts("-1");

        return 0;

    }

    int maxdep = 0;

    for(int i = 1;i <= n;++i)maxdep = max(maxdep,dep[i]);

    int l = 0,r = maxdep * 2,mid;

    while(l < r)

    {

        mid = ((l + r) >> 1);

        if(check(mid))r = mid;

        else l = mid + 1;

    }

    cout << l << endl;

    return 0;

}