【每日一题】倍增专题 疫情控制 题解

Description

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

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

Solution

可以很容易想到答案具有单调性，即当时间到达一定数量时就能够控制疫情，考虑二分答案。
本题的难度在于如何去 答案的合法性。
百思不得其解后，我跑到洛谷看了一篇文章 [https://www.luogu.com.cn/blog/TEoS/p1084-yi-qing-kong-zhi]
画图后发现，根据题意使得从首都到边境城市的每一条路径上都至少有一个检查点，如果在深度低的地方就建立检查点显然是最优的。

如图，在两个根节点的儿子上面建立检查点可以满足题意。所以第一步对每个军队可以根据时间倍增往上跳
此时对每一个根节点的儿子，往下找叶子，判断是否有叶子到根节点的路径上没有军队
如果有的话就要进入第二步操作，有的军队要经过根节点到达根节点的其他儿子，此时我们可以用贪心的思想，优先分配时间充裕的军队到这些有需要的节点。这样我们就完成了对当前二分出来的时间的 。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
typedef long long ll;
vector<pair<int, int> > G[N];
ll dist[N][20], fa[N][20];
int sta[N], dep[N];
int atot = 0, btot = 0, ctot = 0;
ll t;
void bfs(int root) {
  queue<int> q;
  q.push(root);
  while(!q.empty()) {
    int now = q.front(); q.pop();
    for(int i = 1; i < 20; i++) {
      fa[now][i] = fa[fa[now][i - 1]][i - 1];
      dist[now][i] = dist[now][i - 1] + dist[fa[now][i - 1]][i - 1];
    }
    for(auto &x : G[now]) {
      int v = x.first, w = x.second;
      if(v == fa[now][0]) continue;
      fa[v][0] = now;
      dist[v][0] = w;
      q.push(v);
    }
  }
}
bool dfs(int x) {
  bool pos = false;
  if(sta[x]) return true;
  for(auto & u : G[x]) {
    int v = u.first, w = u.second;
    if(v == fa[x][0]) continue;
    pos = true;
    if(!dfs(v)) {
      return false;
    }
  }
  if(!pos) return false;
  return true;
}
int tim[N], ned[N], need[N], m, query[N];
pair<ll, ll> h[N];
bool check(ll lim) {
  memset(sta, 0, sizeof(sta));
  memset(tim, 0, sizeof(tim));
  memset(ned, 0, sizeof(ned));
  memset(h, 0, sizeof(h));
  memset(need, 0, sizeof(need));
  int atot = 0, btot = 0, ctot = 0;
  for(int i = 1; i <= m; i++) {
    ll x = query[i], cnt = 0;
    for(int j = 19; j >= 0; --j) {
      if(fa[x][j] > 1 && cnt + dist[x][j] <= lim) {
        cnt += dist[x][j];
        x = fa[x][j];
      }
    }
    if(fa[x][0] == 1 && cnt + dist[x][0] <= lim) {
      h[++ctot] = make_pair(lim - cnt - dist[x][0], x);
    } else {
      sta[x] = 1;
    }
  }
  for(auto & u : G[1]) {
    if(!dfs(u.first)) {
      need[u.first] = 1;
    }
  }
  sort(h + 1, h + ctot + 1);
  for(int i = 1; i <= ctot; i++) {
    if(need[h[i].second] && h[i].first < dist[h[i].second][0]) {
      need[h[i].second] = 0;
    } else {
      tim[++atot] = h[i].first;
    }
  }
  for(auto & u : G[1]) {
    if(need[u.first]) {
      ned[++btot] = dist[u.first][0];
    }
  }
  if(atot < btot) return false;
  sort(tim + 1, tim + atot + 1), sort(ned + 1, ned + btot + 1);
  int i = 1, j = 1;
  while(i <= btot && j <= atot) {
    if(tim[j] >= ned[i]) {
      i++, j++;
    } else {
      j++;
    }
  }
  if(i > btot) return true;
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  ll left = 0, right = 0;
    bool ok = false;
  for(int i = 1; i <= n - 1; i++) {
    int u, v, w; cin >> u >> v >> w;
    right += w;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  } 
  cin >> m;
    t = log2(n) + 1;
  for(int i = 1; i <= m; i++) cin >> query[i];
  bfs(1); 
  ll ans = -1;
  while(left <= right) {
    ll mid = left + right >> 1;
    if(check(mid)) {
      ans = mid;
      right = mid - 1;
            ok = true;
    } else {
      left = mid + 1;
    }
  }
    if(!ok) {
        cout << -1 << "\n";
    } else { 
      cout << ans << '\n';
    }
    return 0;
}