题意：
H 国有 $n $ 个城市，这 \(n\) 个城市用 $ n-1 $ 条双向道路相互连通构成一棵树，$1 $ 号城市是首都，也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
前言：
一道恶心的贪心题，思路不难想，但实现起来需要注意很多细节。以至于我打完后面部分的代码，就忘了我前面部分写了什么。。。
分析：
显然，对于一个军队，不会存在往下面移动的情况。
考虑二分答案。如何判断 \(x\) 小时是否能控制疫情呢？
对于根首都（根节点）的儿子，我们称为「营地」。
我们把军队分成两类。
- 对于向上走 \(x\) 小时能够走到营地的点，我们称为「闲置军」。
- 否则称为「固定军」。
对于固定军，TA 只需要走到深度最小的点即可。
那么唯一的问题，就是要合理地给一些营地分配一个闲置军。
特殊的，如果一个营地能够通过固定军把该营地管理地所有边境城市都控制住的话，那么这种营地就不需要分配闲置军了。
记 \(need_i\) 表示需要闲置军的营地，\(r_i\) 表示闲置军。
对 \(need\) 按照该营地到根节点的距离从小到大排序，对 \(r\) 按照原军队位置到目前暂存的营地走的距离从小到大排序。
用个双指针随便贪心即可。不过要注意需要特判闲置军在本身子树的情况。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 50004
using namespace std;
int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar('0' + x % 10);
}
int n, d[N]; //d[i]表示i到根节点的距离
int m, s[N], siz[N], dfn[N], cnt, c[N];
int fa[N][21], P[N], tot, G[N], yy[N], son[N];
vector<int>h[N];
struct edge{
int to, w;
};
vector<edge>p[N];
bool lst[N];
bool vis[N];
int PP[N], kk[N];
void dfs(int x, int father) {
fa[x][0] = father;
dfn[x] = ++cnt;
kk[cnt] = x;
siz[x] = 1;
int o = 0;
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i].to;
if(y == father) continue;
son[x]++;
o++;
d[y] = d[x] + p[x][i].w;
yy[y] = p[x][i].w;
if(x == 1) G[y] = y, vis[y] = 1;
else G[y] = G[x];
dfs(y, x);
siz[x] += siz[y];
PP[x] += PP[y];
}
if(o == 0) P[++tot] = x, lst[x] = 1, PP[x] = 1;
}
struct ljm{
int v, w;
}r[N]; //r[i]表示到根节点已经花费的步数
int len;
bool cmp(ljm x, ljm y) {
return x.w < y.w;
}
bool can[N]; //can[i]表示i这个子树的儿子已经铺好了，不用管它
bool nn[N];
bool check(int x) { //最长移动时间在x内是否可行
for(int i = 1; i <= n; i++) c[i] = 0, can[i] = 0, nn[i] = 0;
len = 0;
for(int i = 1; i <= m; i++) {
int now = s[i];
for(int j = 20; j >= 0; j--) {
if(fa[now][j] <= 1 || d[s[i]] - d[fa[now][j]] > x) continue;
now = fa[now][j];
}
if(vis[now]) r[++len] = ((ljm){now, d[s[i]]}); //r[i]存资源
else {
c[dfn[now]]++;
c[dfn[now] + siz[now]]--;
}
}
for(int i = 1; i <= n; i++) c[i] += c[i - 1];
for(int i = 1; i <= n; i++)
if(c[i] >= 1 && lst[kk[i]]) c[i] = 1;
else c[i] = 0;
//cout << "c:";
//for(int i = 1; i <= n; i++) cout << c[i] << " ";
//cout << endl;
for(int i = 1; i <= n; i++) c[i] += c[i - 1];
for(int i = 1; i <= n; i++) {
if(vis[i]) {
if(son[i] == 0) continue;
int res = 0;
for(auto x : p[i]) {
int X = x.to;
if(X == fa[i][0]) continue;
res += PP[X];
}
//cout << i << " : " << res << " " << c[dfn[i] + siz[i] - 1] - c[dfn[i] - 1] << endl;
if(res == c[dfn[i] + siz[i] - 1] - c[dfn[i]]) can[i] = 1;
}
}
vector<ljm>need; //需要帮助的子树
for(int i = 1; i <= n; i++) {
if(vis[i] == 1 && can[i] == 0) need.push_back((ljm){i, yy[i]});
}
vector<int>G[N];
sort(r + 1, r + len + 1, cmp);
for(int i = 1; i <= len; i++) {
G[r[i].v].push_back(i);
}
sort(need.begin(), need.end(), cmp);
//cout << "e";
//for(auto now : need) cout << now.v << " ";
//cout << endl;
/*cout << "oooo";
for(auto now : need) cout << now.v << " ";
cout << endl;
for(int i = 1; i <= len; i++) cout << r[i].v << " ";
cout << endl;*/
int can = len;
for(auto now : need) {
int Get = -1;
while(can) {
if(nn[can] == 1) can--;
else if(r[can].w + now.w <= x) {
Get = can;
break;
}
else can--;
}
//cout << "e" << can << endl;
int o = -1, Max = 0;
for(auto y : G[now.v]) {
if(nn[y]) continue;
if(r[y].w - yy[now.v] <= x) {
if(r[y].w > Max) {
Max = r[y].w;
o = y;
}
}
}
if(o == -1 && Get == -1) { //两个都找不到合适的
return 0;
}
if(o == -1) {
nn[Get] = 1;
}
else if(Get == -1) {
nn[o] = 1;
}
else if(Max > r[Get].w) {
nn[o] = 1;
}
else nn[Get] = 1;
}
return 1;
}
signed main() {
n = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read(), w = read();
p[u].push_back((edge){v, w});
p[v].push_back((edge){u, w});
}
m = read();
for(int i = 1; i <= m; i++) s[i] = read();
dfs(1, 0);
//cout << "PP" << PP[7] << endl;
for(int j = 1; j <= 20; j++)
for(int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
int L = 0, R = 1e14, mid, ans = -1;
while(L <= R) {
mid = (L + R) / 2;
if(check(mid)) {
ans = mid;
R = mid - 1;
}
else L = mid + 1;
}
write(ans);
//cout << check(9);
return 0;
}
/*
4
1 2 1
1 3 2
3 4 3
2
2 2
*/
/*
8
4 1 2
3 4 8
2 1 7
7 8 8
8 4 3
6 1 7
4 5 1
7
6 7 5 6 6 6 6
*/