Description
Luogu1084
给定一棵树和一些军队，军队可以移动，一个军队可以覆盖他的整个子树，求为了使所有叶子节点都被覆盖，移动时间最长的军队最短的移动时间是多少。
Solution
这个题不难想到二分答案，但是二分后如何验证成了一个问题。
首先观察到一个重要的结论：在不超过根节点的前提下，一个军队的深度越浅越好，且没有变深的必要。所以，可以先上提所有军队，直至到达根节点的儿子或者到达上限。
此时一定会有若干个军队尚可移动，将其存入数组(A)中。
对于根的每个儿子，若其子树中的叶子节点全被无法移动的军队覆盖，那么这个儿子不会因给出军队而需要军队，所以就不管了。其他的儿子都放入数组(B)中。
我们先排序(A)，(B)。贪心的处理(B)中的每个元素(b)：如果(b)这棵子树中还有可以移动的军队，那就用剩余时间最短的那个，否则就使用其它子树中剩余时间最长的那个。这样做是一定最优的，可以用交换法证明。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N = 5e4 + 10;
const int M = 2 * N + 10;
int hd[N], to[M], nxt[M], w[M], cnt; // 边表
int n, m, acnt, bcnt; // 点数，边数，A，B数组的大小
int army[N], fa[N][20], vis[N], used[N];
// army 每个军队的位置 fa 每个节点的祖先（倍增）
// vis 某个节点是否有无法移动的军队
// used 某个军队是否被用过
LL dis[N][20]; // 到祖先的距离
struct node {
int id; LL rest;
} a[N], b[N], c[N];
// a A b B c 根的每个儿子节点中可以移动的剩余时间最短的军队
inline void adde(int x, int y, int z) {
cnt++;
to[cnt] = y; w[cnt] = z; nxt[cnt] = hd[x];
hd[x] = cnt;
}
void dfs(int x, int f) { // 处理倍增数组
for (int i = 1; i < 20; ++i) {
fa[x][i] = fa[fa[x][i-1]][i-1];
dis[x][i] = dis[fa[x][i-1]][i-1] + dis[x][i-1];
}
for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {
fa[to[i]][0] = x;
dis[to[i]][0] = w[i];
dfs(to[i], x);
}
}
bool cmp(node x, node y) {
return x.rest > y.rest;
}
bool check_node(int x, int f) { // 检验这个节点的子树是否不需要军队
int is_leave = 1;
int not_child_need_army = 1;
if (vis[x]) return 1;
for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {
is_leave = 0;
if (!check_node(to[i], x)) {
not_child_need_army = 0;
if (x == 1) { // 如果是根的儿子就放入B数组
b[++bcnt].id = to[i];
b[bcnt].rest = w[i];
} else return 0;
}
}
if (is_leave) return 0; // 如果访问到叶子，说明其没有被覆盖
else return not_child_need_army;
}
bool check(LL lim) {
// 初始化
acnt = bcnt = 0;
memset(c, 0, sizeof c);
memset(vis, 0, sizeof vis);
memset(used, 0, sizeof used);
used[0] = 1;
// 移动军队
for (int i = 1; i <= m; ++i) {
int x = army[i];
int num = 0;
for (int j = 19; j >= 0; --j) {
if (num + dis[x][j] <= lim && fa[x][j] > 1) {
num += dis[x][j];
x = fa[x][j];
}
}
if (fa[x][0] == 1 && num + dis[x][0] <= lim) { // 还能走
a[++acnt].rest = lim - dis[x][0] - num; a[acnt].id = i;
if (!c[x].id || c[x].rest > a[acnt].rest) {
c[x].id = a[acnt].id;
c[x].rest = a[acnt].rest;
}
} else { // 不能走
vis[x] = 1;
}
}
if (check_node(1, 0)) return 1;
// 贪心的处理B中的每个元素。
int now = 1;
std::sort(a+1, a+acnt+1, cmp); std::sort(b+1, b+bcnt+1, cmp);
for (int i = 1; i <= bcnt; ++i) {
if (!used[c[b[i].id].id]) {
used[c[b[i].id].id] = 1;
continue;
}
while (now <= acnt && (used[a[now].id] || a[now].rest < b[i].rest)) now++;
if (now > acnt) return 0;
used[a[now].id] = 1;
}
return 1;
}
int main() {
scanf("%d", &n);
LL L = 0, R = 0;
for (int i = 1, x, y, z; i < n; ++i) {
scanf("%d%d%d", &x, &y, &z);
adde(x, y, z);
adde(y, x, z);
R += z;
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &army[i]);
}
dfs(1, 0);
LL ans = -1;
while (L < R) {
LL mid = (L + R) >> 1;
if (check(mid)) {
R = mid;
ans = mid;
} else {
L = mid+1;
}
}
printf("%lld
", ans);
return 0;
}