WA 60求助
查看原帖
WA 60求助
726139
残阳如血楼主2024/4/23 20:47
/*
预处理每一个节点的祖先的倍增数组
考虑二分答案,让所有军队的行动时间不超过 mid
利用倍增快速上移军队,如果能到达根节点且还有甚于时间,考虑可以取其他子树的可能性,留着备用
DFS 查询所有叶子结点,得到根节点哪些子树需要驻扎
贪心完成最后的匹配
*/
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
const int N = 5e4 + 10;

struct edge  {
  int v, w;
};

bool ok[N];
std::vector<edge> g[N];
int n, m, l = -1, r = 1e9, f[N][20], dep[N], s[N], a[N], b[N], need[N];
// s[i] 记录根节点到结点 i 的距离

void init(int u, int fa, int sum) { // 初始化 f, dep, s 数组
  f[u][0] = fa, s[u] = sum, dep[u] = dep[fa] + 1;
  for (int i = 1; i < 20; ++i)
    f[u][i] = f[f[u][i - 1]][i - 1];
  for (auto to : g[u])
    if (to.v != fa) init(to.v, u, sum + to.w);
}

bool dfs(int u) {
  if (ok[u]) return false;
  if (g[u].size() == 1) return true;
  for (auto to : g[u]) {
    if (dep[to.v] < dep[u]) continue;
    if (dfs(to.v)) return true;
  }
  return false;
}

bool check(int k) {
  std::vector<std::pair<int, int>> q;
  std::vector<int> p, dis;
  // p:剩余的时间    dis:剩余的距离
  memcpy(b, a, sizeof(b));
  memset(need, false, sizeof(need));
  memset(ok, false, sizeof(ok));
  for (int i = 1; i <= m; ++i) { // 上移军队
    int &u = b[i], t = k;
    for (int j = 20; ~j; --j)
      if (f[u][j] > 1 && s[u] - s[f[u][j]] <= t) t -= s[u] - s[f[u][j]], u = f[u][j];
    if (dep[u] == 2 && s[u] < t) q.push_back({t - s[u], u});
    else ok[u] = true;
  }
  std::sort(q.begin(), q.end());
  for (auto to : g[1]) // 判断根节点到叶子结点的路径上有没有军队驻扎
    need[to.v] = dfs(to.v);
  for (auto cur : q) { // 已有军队驻扎且当前军队无法到达根节点,驻扎再原处
    if (need[cur.second] && cur.first < s[cur.second]) need[cur.second] = false;
    else p.push_back(cur.first);
  }
  for (auto to : g[1]) // 如果子节点需要驻扎,记录距离
    if (need[to.v]) dis.emplace_back(s[to.v]);
  if (p.size() < dis.size()) return false; // 显然不可以
  std::sort(p.begin(), p.end()), std::sort(dis.begin(), dis.end());
  int pp = 0, disp = 0; // pp 指向 p 数组,disp 指向 dis 数组
  while (pp < p.size() && disp < dis.size()) {
    if (p[pp] >= dis[disp]) ++pp, ++disp;
    else ++pp;
  }
  return disp >= dis.size();
}

void print() {
  puts("");
  for (int i = 1; i <= n; ++i) printf("%2d", i);
  puts("");
  for (int i = 1; i <= n; ++i) printf("%2d", dep[i]);
  puts("");
  for (int i = 1; i < 20; ++i) printf("%3d", i);
  puts("");
  for (int i = 1; i <= n; ++i, puts(""))
    for (int j = 0; j < 20; ++j)
      printf("%3d", f[i][j]);
  puts("");
}

signed main() {
  // std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n;
  for (int i = 1, u, v, w; i < n; ++i) {
    std::cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dep[1] = 1, init(1, 0, 0);
  std::cin >> m;
  for (int i = 1; i <= m; ++i) std::cin >> a[i];
  while (l + 1 != r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid;
  }
  std::cout << (r == 1e9 ? -1 : r) << std::endl;
  // std::cout << check(3) << std::endl;
  return 0;
}
2024/4/23 20:47
加载中...