[NOIP2012] 疫情控制
题目大意：给出一棵树，有(m)个军队在某些结点上，使这个结点的子树都被覆盖，可以在移动军队到某个结点，要求让所有叶子节点都被覆盖。
Solution
注意这几个点
-
所有军队一定是往上走的，如果跨越了根节点，那么一定是在根节点的一个儿子上。
-
因为所有军队都是同时移动的，所以就是使移动时间最长的军队所花的时间最少，是一个二分的思想
那么如何二分？？？
我们在(mid)时间中让每一个军队都往上提，提不动的话就放在那里，那么就会剩下很多可以越过根节点的军队，我们让这些军队和需要军队的结点匹配，就可(check)
- 按照距离根节点的距离，排序所有需要军队的结点；
- 按照剩余时间，排序所有可以到达根节点且有剩余时间的军队；
- 对于一个结点，先尝试我们有剩余时间的，且在这个结点子树内的的军队(a)，如果没有，再考虑剩余时间最长的军队(b)；
- 这对下一个结点(nxt)的匹配是没有影响的；
- 首先(aleq b),如果因为我们选了(a)导致(nxt)无法被匹配，那么说明(b)也无法匹配(nxt)，(a)就更不可能了；
- 如果因为我们选了(b)导致(nxt)无法被匹配，那么说明(a)不存在，我们只能用(b)来匹配当前结点，如果连当前结点都无法匹配，何来(nxt)的匹配。
- 将军队向上提，如果可以提到根节点，且有剩余时间，那么进入数组(a)
- 如果不可以，那就在结束的点上打标记，说明子树已经全部被覆盖
- 对根节点的所有儿子判断是否需要军队，需要军队就进入数组(b)
- 对数组(a,b)进行排序
- 贪心求是否匹配
细节在代码中
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define pf(x) printf("%d
", x);
using std::sort;
const int N = 5e4 + 5;
int head[N], cnt, ans = -1, n, R, L, acnt, bcnt, m;
int ju[N][20], dis[N][20];
int army[N], vis[N], used[N];
struct Edge{
int to, next, val;
}e[N << 1];
struct Aha{
int rest, id;
}a[N], b[N], c[N];
inline void addedge(int x, int y, int z){
e[++cnt].val = z;
e[cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt;
}
inline void init(){
scanf("%d", &n);
for(int i = 1, la, lb, lc; i <= n - 1; ++i){
scanf("%d %d %d", &la, &lb, &lc);
addedge(la, lb, lc);
addedge(lb, la, lc);
R += lc;
}
scanf("%d", &m);
for(int i = 1; i <= m; ++i){
scanf("%d", &army[i]);
}
}
void dfs(int x, int fa){
for(int i = 1; i <= 17; ++i){
ju[x][i] = ju[ju[x][i - 1]][i - 1];
dis[x][i] = dis[ju[x][i - 1]][i - 1] + dis[x][i - 1];//dis[x][i]表示从x点调2 ^ i个点所需的时间
}
for(int i = head[x]; i; i = e[i].next){
if(e[i].to != fa){
dis[e[i].to][0] = e[i].val;
ju[e[i].to][0] = x;
dfs(e[i].to, x);
}
}
return;
}
bool check_node(int x, int fa){
int child_flag = 0;
int common_child_flag = 1;
if(vis[x]) return 1;//如果已经有不能跳到根节点的军队在这里驻扎，直接返回true
for(int i = head[x]; i; i = e[i].next){
if(e[i].to != fa){
child_flag = 1;
if(!check_node(e[i].to, x)){
common_child_flag = 0;
if(x == 1){//如果是根节点的儿子，进入数组b
b[++bcnt].id = e[i].to;
b[bcnt].rest = e[i].val;
}
else return 0;
}
}
}
if(!child_flag) return 0;
else return common_child_flag;//如果是根节点，由于在统计儿子时不能直接返回0，所以如果有了需要军队的，便变为0
//同时当普通点如果一直子节点都返回1，那么最终也是返回1的
}
inline bool cmp(Aha c, Aha d){
return c.rest > d.rest;
}
bool check(int lim){
int num;
acnt = 0, bcnt = 0;
used[0] = 1;//一定别忘qwq
for(int i = 1; i <= n; ++i) vis[i] = 0;
memset(c, 0, sizeof(c));//初始化
for(int i = 1; i <= m; ++i) used[i] = 0;
for(int i = 1, x; i <= m; ++i){
x = army[i];//取军队的位置
num = 0;
for(int j = 17; j >= 0; --j){
if(num + dis[x][j] <= lim && ju[x][j] > 1){
num += dis[x][j];
x = ju[x][j];
}
}
if(ju[x][0] == 1 && num + dis[x][0] <= lim){
a[++acnt].rest = lim - num - dis[x][0], a[acnt].id = i;
if(!c[x].id || a[acnt].rest < c[x].rest)
c[x].id = a[acnt].id, c[x].rest = a[acnt].rest;
} else {
vis[x] = 1;
}
}
int now = 1;
if(check_node(1, 0)) return 1;
sort(a + 1, a + acnt + 1, cmp), sort(b + 1, b + bcnt + 1,cmp);//由于一个是取剩余时间的从大到小，一个是取剩余距离的从大到小，我们可以合成一个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;
}
void b_s(){
int mid;
while(L <= R){
mid = L + ((R - L) >> 1);
if(check(mid)){
ans = mid;
R = mid - 1;
}else {
L = mid + 1;
}
}
}
inline void outit(){
printf("%d
", ans);//无解输出-1
}
int main(){
init();//读入
dfs(1, 0);//深搜一遍处理倍增
b_s();//二分求答案
outit();//输出答案
return 0;
}