The 2023 ICPC Asia Hangzhou Regional Contest F

Link：https://codeforces.com/gym/492111/problem/F

知识点：二分答案，树上问题，RMQ 求 lca

对于查询距离某个点长度不大于某个值的题启发性的题。

才知道题名就是树分块的意思妈的，但是这题数据范围把树分块卡掉了哈哈。

这辈子第一次见到不得不用 RMQ 求 lca 的情况、、、

简述

给定一棵大小为 \(n\) 的树，点有点权 \(w_i\) 且保证点权两两不同，边有边权 \(l_i\)。
给定 \(q\) 次操作，每次操作给定参数 \(x, k\) 询问所有距离 \(x\) 不大于 \(k\) 的点点权和的 \(\operatorname{mex}\)，即：\(\operatorname{mex}(\{ w_u | \operatorname{dis}(u, x) \le k \land 1\le u\le n \})\)。
\(1\le n,q\le 5\times 10^5\)，\(0\le w_i\le 10^9\)，\(1\le l_i\le 10^9\)，\(1\le x\le n\)，\(0\le k\le 10^{15}\)。
4S，1024MB。

分析

对于此题非常重要的典中典之直径结论：距离树上某点最远的点一定是直径的端点。

发现对于每次询问答案具有单调性，考虑二分枚举 \(mid\) 并检查 \(x\) 距离点权值 \(0\sim mid\) 的点是否均小于等于 \(k\)。

这东西一眼很不可检查的样子，但是可以考虑构建一棵包含点权值 \(0\sim mid\) 的最小的子树，即按顺序枚举点权值 \(0\sim mid\) 对应节点，并将它与之前节点构成的连通块通过唯一的路径连接，则上述检查等价于检查 \(x\) 到子树中所有节点距离是否不大于 \(k\)。

虽然 \(x\) 不一定在这棵子树上，但是由结论+手玩下可知距离 \(x\) 最远的点还是子树直径的端点，仅需检查 \(x\) 与直接两端点的距离是否不大于 \(k\) 即可。

于是考虑先预处理权值为 \(0\sim i\) 的节点组成的子树的直径，按顺序枚举节点并考虑加入对直径的影响，由上述结论可知，新直径要么不变，要么只是一端被替换成新加入的节点，讨论即可维护。

注意这题每次二分答案检查时都需要求距离，若查询距离的复杂度是 \(O(\log n)\) 则总时间复杂度是 \(O(n\log n + q\log^2 n)\) 级别的，过不去。则必须用 RMQ \(O(n\log n)-O(1)\) 地求两点距离。

则总时间复杂度 \(O((n+q)\log n)\) 级别。

代码

//知识点：二分答案，树上问题，RMQ 求 lca
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 5e5 + 10;
//=============================================================
int n, q, a[kN];
int edgenum, head[kN], v[kN << 1], w[kN << 1], ne[kN << 1];
int fa[kN], sz[kN], dep[kN], son[kN], top[kN];
LL dis[kN], dd[kN];

int pos[kN], maxans;
pr <int, int> d[kN];
//=============================================================
inline LL read() {
  LL f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3ll) + (w << 1ll) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_, int w_) {
  v[++ edgenum] = v_;
  w[edgenum] = w_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
namespace ST {
  int num, Log2[kN << 1], f[kN << 1][20], fir[kN];
  void Dfs(int u_, int fa_) {
    dep[u_] = dep[fa_] + 1;
    fir[u_] = ++ num;
    f[num][0] = u_;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (v_ == fa_) continue ;
      dis[v_] = dis[u_] + 1ll * w_;
      Dfs(v_, u_);
      f[++ num][0] = u_;
    }
  }
  void Prepare() {
    Dfs(1, 1);
    Log2[1] = 0;
    for (int i = 2; i <= num; ++ i) {
      Log2[i] = Log2[i >> 1] + 1; 
    }
    for (int i = 1; i <= 19; ++ i) {
      for (int j = 1; j + (1 << i) - 1 <= num; ++ j) {
        if (dep[f[j][i - 1]] < dep[f[j + (1 << (i - 1))][i - 1]]) {
          f[j][i] = f[j][i - 1];
        } else {
          f[j][i] = f[j + (1 << (i - 1))][i - 1];
        }
      }
    }
  }
  int Lca(int u_, int v_) {
    int l = fir[u_], r = fir[v_];
    if (l > r) std::swap(l, r);
    int lth = Log2[r - l + 1];
    if (dep[f[l][lth]] < dep[f[r - (1 << lth) + 1][lth]]) {
      return f[l][lth];
    }
    return f[r - (1 << lth) + 1][lth];
  }
  LL Dis(int u_, int v_) {
    return dis[u_] + dis[v_] - 2ll * dis[Lca(u_, v_)];
  }
}
void Init() {
  n = read(), q = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    if (a[i] <= n) pos[a[i]] = i;
  }
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read(), w_ = read(); 
    Add(u_, v_, w_), Add(v_, u_, w_);
  }
  ST::Prepare();

  for (int i = 0; i <= n; ++ i) {
    if (!pos[i]) {
      maxans = i;
      break;
    }
    if (i == 0) {
      d[i] = mp(pos[i], pos[i]);
      dd[i] = 0;
    } else if (i == 1) {
      d[i] = mp(pos[0], pos[1]);
      dd[i] = ST::Dis(pos[0], pos[1]);
    } else {
      LL d1 = dd[i - 1];
      LL d2 = ST::Dis(pos[i], d[i - 1].first);
      LL d3 = ST::Dis(pos[i], d[i - 1].second);
      dd[i] = std::max(d1, std::max(d2, d3));
      if (dd[i] == d1) d[i] = d[i - 1];
      if (dd[i] == d2) d[i] = mp(d[i - 1].first, pos[i]);
      if (dd[i] == d3) d[i] = mp(d[i - 1].second, pos[i]);
    }
  }
}
bool check(int x_, LL k_, int mid_) {
  LL d1 = ST::Dis(x_, d[mid_].first);
  LL d2 = ST::Dis(x_, d[mid_].second);
  return d1 <= k_ && d2 <= k_;
}
int Query(int x_, LL k_) {
  int ans = maxans;
  for (int l = 0, r = maxans - 1; l <= r; ) {
    int mid = (l + r) >> 1;
    if (check(x_, k_, mid)) {
      l = mid + 1;
    } else {
      ans = mid;
      r = mid - 1;
    }
  }
  return ans;
}
//=============================================================
int main() {
  Init();
  for (int i = 1; i <= q; ++ i) {
    int x = read(); LL k = read(); 
    printf("%d\n", Query(x, k));
  }
  return 0;
}