题目大意
给出一棵n个节点的树，根是1，要在除根节点以外的点建立检查点，使得从每条根到叶子的路径上都至少存在一个检查点。检查点由军队来建立。初始军队的位置是给定的，移动军队走一条边需要花费这条边的权值的时间。现在要求一个方案，移动军队到某个最佳位置，使得总用时最少。
【数据范围】
保证军队不会驻扎在首都。
对于20%的数据，2≤ n≤ 10；
对于40%的数据，2 ≤n≤50，0<w <105；
对于60%的数据，2 ≤ n≤1000，0<w <106；
对于80%的数据，2 ≤ n≤10,000；
对于100%的数据，2≤m≤n≤50,000，0<w <109。
首先确定思路是二分。
然后关键是怎么check
每个军队肯定是要尽量往上走的。把军队分为走得到root和走不到两种情况。
把仅通过走不到root的军队就能控制的第二层的结点去掉，剩下的就需要通过剩下的军队来控制。
每个军队都要匹配一个结点，排序完直接匹配就可以了。但是这里有一个细节，就是如果一个军队要控制自己所属的结点，就不需要再额外添加时间。
于是我们可以先按军队剩余时间从小到大排，再按需要的时间排序没控制的结点，然后决定每一个军队控制哪个结点。由于已经排过序了，所以当前军队肯定是最没用的。所以如果他所属的结点未被控制，就让他去肯定是最好的方案。
还有一个问题。怎么得出那些结点没被控制？这个有几个方法，可以用倍增直接暴力把军队推上去，还有就是用拓扑排序。
这里介绍下拓扑的方法：
对于每一个结点记录所有军队往上走走到这里剩余时间的最大值time[]。再记一个能否到达arr[]，如果time[u] >= 0则arr[u] = true；如果u的所有儿子都可控制，则arr[u] = true；否则都是false
然后问题就解决了！时间复杂度O(n*log2n)
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
const int N = 50000 + 9;
int ec,n,q[N],mark[N],army[N],t1[N],t2[N],ance[N],father[N],son[N],m,times;
ll dis[N],time[N],cost[N];
bool notleaf[N],arr[N],can_use[N];
struct edge{int next,link,w;}es[N*2];
inline bool cmp1(const int i,const int j){return cost[i] < cost[j];}
inline bool cmp2(const int i,const int j){return dis[army[i]] > dis[army[j]];}
inline void addedge(const int x,const int y,const int z)
{
es[++ec].next = son[x];
son[x] = ec;
es[ec].link = y;
es[ec].w = z;
}
inline void Addedge(const int x,const int y,const int z){addedge(x,y,z),addedge(y,x,z);}
bool check(const ll mid)
{
++times;
memset(time,-1,sizeof(*time)*(n + 1));
memcpy(arr,notleaf,sizeof(*arr)*(n + 1));
memset(can_use,0,sizeof(*can_use)*(m + 1));
for (int i = n; i; --i) {
const int u = q[i];
if (mark[u] && dis[u] > mid) time[u] = mid;
if (time[father[u]] < time[u] - cost[u])
time[father[u]] = time[u] - cost[u];
if (time[u] >= 0) arr[u] = true;
if (!arr[u]) arr[father[u]] = false;
}
for (int i = 1; i <= m; ++i)
if (dis[army[i]] <= mid) can_use[i] = true;
t1[0] = t2[0] = 0;
for (int i = son[1]; i; i = es[i].next)
if (!arr[es[i].link]) t1[++t1[0]] = es[i].link;
for (int i = 1; i <= m; ++i)
if (can_use[i]) t2[++t2[0]] = i;
std::sort(t1 + 1,t1 + 1 + t1[0],cmp1);
std::sort(t2 + 1,t2 + 1 + t2[0],cmp2);
for (int i = 1,j = 1; i <= t2[0]; ++i) {
if (!arr[ance[army[t2[i]]]])
arr[ance[army[t2[i]]]] = true;
else if (cost[t1[j]] + dis[army[t2[i]]] <= mid) arr[t1[j]] = true;
while (j <= t1[0] && arr[t1[j]]) ++j;
if (j > t1[0]) return true;
}
return false;
}
void BFS(const int s)
{
int h = 1,t = 0;
q[++t] = s;
while (h <= t) {
const int u = q[h++];
notleaf[u] = false;
for (int i = son[u]; i; i = es[i].next) {
const int v = es[i].link;
if (v == father[u]) continue;
dis[v] = dis[u] + es[i].w;
father[v] = u;
cost[v] = es[i].w;
if (u != s) ance[v] = ance[u];
else ance[v] = v;
q[++t] = v;
notleaf[u] = true;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("blockade.in","r",stdin);
freopen("blockade.out","w",stdout);
#endif
scanf("%d",&n);
ll r = 1,l = 0,tot = 0;
for (int i = 1,x,y,z; i < n; ++i) {
scanf("%d%d%d",&x,&y,&z);
r += z;
Addedge(x,y,z);
}
tot = r;
scanf("%d",&m);
for (int i = 1; i <= m; ++i) {
scanf("%d",army + i);
mark[army[i]] = i;
}
BFS(1);
while (l + 1 < r) {
const ll mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid;
}
if (r == tot) puts("-1");
else printf("%I64d\n",r);
//check(9);
}