疫情控制

题意&分析在进阶指南上面已经讲解的很详细了，所以这里长话短说记录一下整体思路和从思路到代码的过渡部分

思路

1. 答案单调性 -> 二分答案判定
2. 军队驻扎的点越靠近根结点，即越靠上，越能管辖更多的点，根据二分枚举的值使得军队尽量往根结点走
3. 对于可以到达根结点，并且窜到其他子树的军队，分析其窜位的必要性。蓝书巧妙的证明了当该军队不足以到达根结点后再返回到原子树根结点时，在最优解中该军队不会窜到其他子树中。用一句话理解就是，它窜走了之后其他子树上的军队还要窜到它的位置上，总的资源一定的情况下，这样做是毫无必要的。
4. 将可以窜到其他子树的军队筛选出来，将没有覆盖的子树根结点筛选出来，排序，双指针贪心扫描即可。

代码实现

1. 如何往上走？ 考虑倍增求lca的过程
2. 如何筛选H集合（即叶子结点尚未被管辖的son(root))? 将无法跳到根结点的军队最终的位置（最后跳到的位置）标记一下，然后dfs处理，dfs处理的时候要看个人的编码习惯注意一些细节。
3. 如何筛选可以窜位的军队？记录每个可以跳到根结点的军队原所在子树的根结点x以及跳到结点1后所剩的时间，如果所剩时间不足以从1返回x，那么就把这个军队删除。(军队ID没有必要保存)

PS: 感谢 __76 同学的提醒，这里筛选可以篡位的军队时，要先按照剩余时间对军队排序，再从小到大依次考虑剔除。

其他细节：
1. 删除的时候可以直接用数组，用一个指针np记录新数组的长度，遇到不被删除的元素时可以array[np++] = array[i]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50000 + 5;

int n, m, pos[N], ok[N], head[N], ver[N << 1], edge[N << 1], nxt[N << 1], tot;
int f[N][20];
ll d[N][20];
void add(int x, int y, int z)
{
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
void pre(int x,int fa){
    for (int i = head[x]; i;i=nxt[i]){
        int y = ver[i];
        if(y == fa)
            continue;
        d[y][0] = edge[i];
        f[y][0] = x;
        pre(y, x);
    }
}
bool getOK(int x,int fa){
    if(ok[x])
        return true;
    int cnt = 0;//记录x子结点个数
    for (int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(y == fa)
            continue;
        if(!getOK(y,x))
            return false;
        cnt++;
    }
    /*如果x是叶子结点，那么返回false*/
    if(cnt)
        return ok[x] = 1;
    else
        return false;
}
bool check(ll mid){
    //cout << mid << endl;
    for(int i=1;i<=n;i++)ok[i] = 0;
    vector<pair<ll, int> > ss;
    vector<pair<ll, int> > H;
    for (int i = 1; i <= m; i++)
    {
        int cur = pos[i];
        ll now = mid;//现在所剩下的时间
        for (int j = 19; j >= 0; j--){
            if(f[cur][j] != 1 && d[cur][j] <= now){
                now -= d[cur][j];
                cur = f[cur][j];
            }
        }
        if (f[cur][0] == 1)
        { // 能够登顶, 登顶之后的剩余时间
            ss.push_back({now - d[cur][0], cur});
        }
        else//不能登顶，停留在这里
            ok[cur] = 1;
    } 
    for (int i = head[1]; i;i = nxt[i]){
        int y = ver[i];
        getOK(y, 1);
    }
    int np = 0;
    sort(ss.begin(), ss.end());
    for (int i = 0; i < ss.size(); i++){
        int y = ss[i].second;
        ll rest = ss[i].first;
        if(ok[y] || rest >= d[y][0]){ //能够从1返回到原子树根结点
            ss[np++] = ss[i];
            continue;
        }else{//否则留在y点
            ok[y] = 1;
        }
    }
    for (int i = head[1]; i; i=nxt[i]){
        int y = ver[i];
        if(!ok[y])
            H.push_back({edge[i], y});
    }
    sort(H.begin(), H.end());
    int j = 0; // 双指针贪心扫描
    for (int i = 0; i < H.size(); i++){
        int y = H[i].second;
        while(j < np && ss[j].first < H[i].first)
            j++;
        if(j == np)
            return false;
        j++;
    }
    return true;
}
int main() {
    scanf("%d", &n);
    ll l = 0, r = 0;
    for (int i = 1; i < n; i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
        r += z;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m;i++){
        scanf("%d", &pos[i]);
    }
    f[1][0] = 1;
    pre(1, 0);
    for (int j = 1; j <= 19;j++){
        for (int i = 1; i <= n;i++){
            f[i][j] = f[f[i][j-1]][j-1];
            d[i][j] = d[i][j-1] + d[f[i][j-1]][j-1];
        }
    }
    while (l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
            l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}