题意

给你一棵有 个节点的树，要求在所有叶子节点到根节点的路径上有一个节点是特殊的（军队）。问如果要封死这棵树，移动距离最大的点移动的最小距离是多少？

分析

这题挺恼火的，一步一步慢慢来

首先：树上倍增先预处理
用存储 节点的第 个祖先的节点编号， 存储 节点到它的第 个祖先的路径长度。在预处理过程中同时也处理出每个节点的深度，用 表示。
递推式：

然后：二分答案
因为时间越长显然就越容易实现，所以答案具有单调性。

再接着：重点就是check函数了
如何判断一个时间限制符不符合条件呢？显然，对于所有军队，我们希望它最后停留的节点深度越小越好，这样可以控制最多的路径。因此我们让所有的军队尽量地向上走，若一个军队可以走到根节点，则令其暂时停在根节点的子节点；否则走到时间限制内能够走到的深度最小的节点。这个步骤可以用树上倍增进行优化。

我们先找出所有以根节点的子节点为根的子树中，是否有到叶子节点的路径还未被驻扎，并记录下还有路径未被驻扎的这些子树的根节点。对于这些节点，可以证明，若该节点上停留有军队，则剩余时间最小的军队驻扎在该节点一定是最优的。这样处理过这些节点后，把剩下的节点按照到根节点的距离从小到大排序。

现在可能还会有一些军队未确定最后的驻扎节点，把这些军队按照剩余时间从小到大排序，然后和上一步处理出来的这些节点一一进行匹配。这是一个可以证明正确性的贪心策略。若所有未被驻扎的节点都有军队驻扎，则说明当前的时间限制可行；反之则不可行。

我太难啦，大概就是这样啦。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e5+5,INF=0x3f3f3f3f;
using namespace std;

int n,m,t,tot=0,atot=0,btot=0,ctot=0;
int d[N],query[N],f[N][20];
int ver[2*N],edge[2*N],Next[2*N],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;

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}

void bfs()
{
    q.push(1);
    d[1]=1;
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[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);
        }
    }
}

bool dfs(int x)
{
    bool pson=0;
    if(sta[x])    return 1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(d[y]<d[x])    continue;
        pson=1;
        if(!dfs(y))    return 0;
    }
    if(!pson)    return 0;
    return 1;
}

void cl()
{
    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 check(ll lim)
{
    cl();
    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=Next[i])
     if(!dfs(ver[i]))
      need[ver[i]]=1;
    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=Next[i])
     if(need[ver[i]])
      ned[++btot]=dist[ver[i]][0];
    if(atot<btot)    return 0;
    sort(tim+1,tim+1+atot),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()
{
    ll l=0,r=0,mid;
    n=read();
    t=log2(n)+1;
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,z);
        r+=z;
    }
    bfs();
    m=read();
    for(int i=1;i<=m;i++)
        query[i]=read();
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
            ok=1;
        }
        else
            l=mid+1;
    }
    if(!ok)    printf("-1");
    else    printf("%lld",ans); 
    return 0;
}