疫情控制

题面

H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。

当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。

但要注意的是，首都是不能建立检查点的。

现在，在H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。

军队总数为 m 支。

一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。

一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问：最少需要多少个小时才能控制疫情？

注意：不同的军队可以同时移动。

输入格式

第一行一个整数n，表示城市个数。

接下来的n-1行，每行3个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市u到城市v有一条长为w的道路，数据保证输入的是一棵树，且根节点编号为1。

接下来一行一个整数m，表示军队个数。

接下来一行m个整数，每两个整数之间用一个空格隔开，分别表示这m个军队所驻扎的城市的编号。

输出格式

共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

数据范围

2≤m≤n≤50000,
0<w<109

输入样例：

输出样例：

题解

来自蓝书树上LCA最后一题

贪心的想, 检查的点越靠近根节点, 管的叶子节点越多

然后发现, 对于答案是单调的, t时刻能完成, t + k也能(二分)

然后是怎么check

我们想要覆盖住所有的子节点, 相当于覆盖住所有的根节点的son

对于无法对其他根节点的son的做贡献的军队, 我们尽量向上走, 当节点a 的所有 son 被检查的时候, 就可以覆盖节点a, 向上递归, 当递归到根节点son, 对答案就有贡献了

能对根节点其他son做贡献的, 就排序, 去对没被覆盖的根节点son(排序) 做贡献 (贪心, 尽量让时间短的去覆盖近的son)

小贪心: 能覆盖其他son, 但是这支军队到了根节点无法再返回这支军队原所在的根节点的son, 且原根节点的son没被覆盖, 直接让这个军队呆在原根节点son
(没这步也行, 你只能覆盖到根节点距离小于自身到跟跟根节点距离的son, 你去覆盖别人, 别人覆盖你, 那你直接别动, 让别人去覆盖别人就行)

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 5e4 + 5;

int n, m, _, k;
int h[N], ne[N << 1], to[N << 1], co[N << 1], tot;
int f[N][20], dep[N], dist[N], fa[N], t;
bool v[N];
vector<PII> a, b;
VI c;

void add(int u, int v, int c) {
    ne[++tot] = h[u]; h[u] = tot; to[tot] = v; co[tot] = c;
}

void bfs(int s) {
    queue<int> q;
    q.push(s); dep[s] = 1; dist[s] = 0;

    while (!q.empty()) {
        int x = q.front(); q.pop();

        if (!ne[h[x]]) { c.pb(x); continue; }

        for (int i = h[x]; i; i = ne[i]) {
            int y = to[i];
            if (dep[y]) continue;
            dep[y] = dep[x] + 1;
            fa[y] = x == s ? y : fa[x];
            dist[y] = dist[x] + co[i];
            f[y][0] = x;

            for (int j = 1; j <= t; ++j)
                f[y][j] = f[f[y][j - 1]][j - 1];

            q.push(y);
        }
    }
}

int ask(int a, int b) {
    per(i, t, 0)
        if (dist[a] - dist[f[a][i]] <= b) b -= dist[a] - dist[a = f[a][i]];
    return a;
}

void change(int k) {
    if (f[k][0] == 1) return;
    k = f[k][0];
    for (int i = h[k]; i; i = ne[i])
        if (!v[to[i]] && to[i] != f[k][0]) return;
    v[k] = 1;
    change(k);
}

bool check(int mid) {
    vector<PII> s;
    memset(v, 0, sizeof v);

    for (PII i : a) {
        int idx = i.se;
        if (idx == 1) s.pb({ mid, 1 });
        else if (mid <= dist[idx] + dist[fa[idx]]) {
            if (mid < dist[idx] - dist[fa[idx]]) {
                v[idx = ask(idx, mid)] = 1;
                change(idx);
            }
            else if (!v[fa[idx]]) v[fa[idx]] = 1;
            else if (mid > dist[idx]) s.pb({ mid - dist[idx], idx });
        }
        else s.pb({ mid - dist[idx], idx });
    }

    sort(all(s));
    int j = -1;
    for (PII i : b)
        if (!v[i.se]) {
            while (++j < s.size() && s[j].fi < i.fi);
            if (j == s.size()) return 0;
        }
    return 1;
}

int main() {
    IO; cin >> n;
    t = log2(n - 1) + 1;
    rep(i, 2, n) {
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c); add(v, u, c);
    }
    bfs(1);
    cin >> m; a.resize(m);
    rep(i, 0, m - 1) cin >> a[i].se, a[i].fi = dist[fa[a[i].se]] - dist[a[i].se];
    sort(all(a));

    for (int i = h[1]; i; i = ne[i]) b.pb({ dist[to[i]], to[i] });
    sort(all(b));

    int l = 0, r = 0x7f7f7f7f;
    while (l < r) {
        int mid = (ll)l + r >> 1;
        if (check(mid)) r = mid;
        else 
            l = mid + 1;
    }
    cout << l;
    return 0;
}