题意
一棵 $n(\le 50000)$ 个点的树，有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守，军队可以同时移动，每小时移动 $1$ 单位长度。问至少要多久才能满足条件，无解输出 。-1（没有）
题解
答案显然满足单调性，所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)
如果军队 $i$ 在根节点到叶子节点 $j$ 的路径上，就称 $i$ 管辖了 $j$ 。可以发现深度越小，管辖的节点越多，所以可以先把节点尽量往上提。(2)
令根节点的子节点组成的集合为 $S$ 。如果某支军队到不了根，就让它停下并驻守在最远能到达的位置；如果能到根，那么它就可能可以跨过根节点去管辖其它节点，不过先让它停在能到达的 $S$ 上，并记录它所在的位置和还能走的距离为 $u$ 。然后将这些军队按照还能走的距离排序。(3)
然后以各个 $S$ 为起点进行搜索，得到以它们为根的子树的叶节点是否全部被管辖，并记录为 $res[i]$ 。(4)
然后按排序后的顺序遍历 $u$ ，如果存在某支军队 $i$ 所在的节点还没被覆盖，并且它不能走到根节点并回到这里，就让它驻守在这里，并从 $u$ 中把它删去。(5)
因为它不能再回到这里，所以它跨过根节点后也只能去管辖一个离根节点更近的 $S$ ，同时需要有一个 $i'$ 来管辖这里。这个 $i'$ 剩下的距离就一定 $> i$ ，所以不如把 $i$ 留在这里，让 $i'$ 去覆盖其它节点。
这一步后把子树还是没被完全管辖的 $S$ 记录进 $v$ ，并按照它到根的距离排序。(6)
然后遍历所有的 $u$ 和 $v$ ，按贪心的思想依次管辖，如果所有的 $v$ 都被管辖那么就满足条件。(7)
可以发现需要预处理出倍增的祖先节点数组 $fa[i][j]$ 和与祖先节点之间的距离 $dis[i][j]$ 。(8)
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<ll,int>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=50005;
struct Edge {
int next,to,w;
} edge[N<<1];
ll dis[N][17];
bool vis[N],res[N],del[N];
int cnt,head[N],n,m,a,b,c,s[N],fa[N][17];
inline void add(int u,int v,int w)
{
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int x,int f,int di) //(8)：倍增预处理
{
fa[x][0]=f;
dis[x][0]=di;
for (int i=1;i<=16;i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
dis[x][i]=dis[x][i-1]+dis[fa[x][i-1]][i-1];
}
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs(y,x,edge[i].w);
}
}
bool dfs2(int x,int f)
{
if (vis[x]) return 1; //有军队驻守
bool flag=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
flag=1; //不是叶子节点
if (!dfs2(y,x)) return 0;
}
return flag; //如果都访问到叶子节点了那就返回false
}
inline bool check(ll mid)
{
vector <pii> u,v;
memset(vis,0,sizeof(vis));
memset(del,0,sizeof(del));
for (int i=1;i<=m;i++)
{
int x=s[i]; ll dsum=0;
for (int j=16;~j;j--) //(2)：尽量往上提
{
if (fa[x][j]<=1 || dsum+dis[x][j]>mid) continue;
dsum+=dis[x][j];
x=fa[x][j]; //注意这两句话的顺序
}
if (fa[x][0]==1 && dsum+dis[x][0]<=mid) u.push_back(mp(mid-dsum-dis[x][0],x)); //(3)：记录能到根的节点
else vis[x]=1; //(3)：不能到根就驻守在这
}
sort(u.begin(),u.end()); //(3)：按还能走的距离排序
for (int i=head[1];i;i=edge[i].next) //(4)：得到各个S的子树是否被管辖
{
int x=edge[i].to;
res[x]=dfs2(x,1);
}
for (unsigned int i=0;i<u.size();i++) //(5)
{
int x=u[i].second,w=u[i].first;
if (!res[x] && w<dis[x][0]) //没被管辖，且自己管辖更优
{
vis[x]=res[x]=1;
del[i]=1; //删掉
}
}
for (int i=head[1];i;i=edge[i].next) //(6)
{
int x=edge[i].to;
if (!res[x]) v.push_back(mp(edge[i].w,x));
}
sort(v.begin(),v.end()); //(6)：按到根的距离排序
bool ans=1;
for (unsigned int i=0,j=0;i<v.size();i++) //(7)
{
for (;j<u.size() && (u[j].first<v[i].first || del[j]);j++);
if (j==u.size()) { ans=0; break; } //找不到能管辖的了
j++; //使用 Uj 管辖 Vi
}
return ans;
}
signed main()
{
n=read();
ll l=0,r=0;
for (int i=1;i<n;i++)
{
a=read(); b=read(); c=read();
r+=c;
add(a,b,c);
add(b,a,c);
}
m=read();
for (int i=1;i<=m;i++) s[i]=read();
dfs(1,0,0);
while (l<r) //(1)：二分答案
{
ll mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
return !printf("%lld",l);
}