QOJ #5439. Meet in the Middle 题解

Description

Byteland 有 $n$ 座城市，从 $1$ 到 $n$ 编号，且有 $n-1$ 条双向公路和 $n-1$ 条双向铁路连接它们。

对于任意一对城市，都可以仅通过公路互相到达；同样，仅通过铁路也能互相到达。

Alice 和 Bob 计划在 Byteland 进行 $q$ 次长途旅行。在每次旅行中，Alice 从第 $a$ 座城市出发，只通过公路访问一些其他城市；Bob 从第 $b$ 座城市出发，只通过铁路访问一些其他城市。

两人最终会在同一座目的城市会合，并且在整个旅途中都不会重复访问任何城市。

你需要求出，在所有目的城市的选择中，他们路线总长度的最大值。

$n\leq 10^5,q\leq 5\times 10^5$。

Solution

首先对于一棵树，每次求距离某个点最远的点，有两种做法，第一种是离线下来用数据结构维护距离；第二种方法是由于最远的点一定是直径端点，所以可以求出全局直径后 $O(1)$ 做。

这里有两棵树，用某一种方法都不太好做，考虑将这两种方法结合起来。

先把询问离线下来，对第一棵树做第一种方法，即按照 dfs 的顺序枚举询问在第一棵树的点 $x$，在移动的过程中维护 $w_i$ 表示 $i$ 与 $x$ 的距离。

现在问题等价于求 $w_i+dis_2(i,y)$ 的最大值，这个对第二棵树的每个点 $j$，建立一个虚点 $j'$，与 $j$ 连边权值为 $w_j$ 就能将问题转化为直径问题。

但是移动 $x$ 的过程中 $w_i$ 会变化，考虑用线段树维护子树内节点的直径。

注意到线段树修改的过程是找到若干个线段树区间 $[l,r]$ 再区间打标记，由于整体打标记不会影响直径，所以找到这些区间后向上合并直径就行了。

时间复杂度：$O(n\log n+q)$。

Code

#include <bits/stdc++.h>

#define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 1e5 + 5, kMaxQ = 5e5 + 5;

int n, q, pos;
int res[kMaxQ];
std::vector<std::pair<int, int>> qq[kMaxN];

struct Tree {
  int dfn_cnt, dfn[kMaxN], idx[kMaxN], sz[kMaxN], dis[kMaxN], st[kMaxN][18];
  std::vector<std::pair<int, int>> G[kMaxN];
  int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
  void add(int u, int v, int w) { G[u].emplace_back(v, w), G[v].emplace_back(u, w); }
  void dfs(int u, int fa) {
    st[dfn[u] = ++dfn_cnt][0] = fa, idx[dfn_cnt] = u, sz[u] = 1;
    for (auto [v, w] : G[u]) {
      if (v == fa) continue;
      dis[v] = dis[u] + w;
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
  int LCA(int x, int y) {
    if (x == y) return x;
    if (dfn[x] > dfn[y]) std::swap(x, y);
    int k = std::__lg(dfn[y] - dfn[x]);
    return get(st[dfn[x] + 1][k], st[dfn[y] - (1 << k) + 1][k]);
  }
  int getdis(int x, int y) { return dis[x] + dis[y] - 2 * dis[LCA(x, y)]; }
  void prework() {
    dfn_cnt = 0, dfs(1, 0);
    for (int i = 1; i <= std::__lg(dfn_cnt); ++i)
      for (int j = 1; j <= dfn_cnt - (1 << i) + 1; ++j)
        st[j][i] = get(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
  }
} t1, t2;

int calc(int x, int y) { return t1.getdis(pos, x) + t1.getdis(pos, y) + t2.getdis(x, y); }

pii merge(pii a, pii b) {
  if (!a.first) return b;
  if (!b.first) return a;
  std::vector<int> vec = {a.first, a.second, b.first, b.second};
  pii ret = {0, 0};
  int now = -1e9;
  for (int i = 0; i < 4; ++i) {
    for (int j = i + 1; j < 4; ++j) {
      int val = calc(vec[i], vec[j]);
      if (val > now) ret = {vec[i], vec[j]}, now = val;
    }
  }
  return ret;
}

struct SGT {
  pii t[kMaxN * 4];
  void pushup(int x) { t[x] = merge(t[x << 1], t[x << 1 | 1]); }
  void build(int x, int l, int r) {
    if (l == r) return void(t[x] = {t1.idx[l], t1.idx[l]});
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void update(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return;
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr), update(x << 1 | 1, mid + 1, r, ql, qr);
    pushup(x);
  }
} sgt;

void dfs(int u, int fa) {
  for (auto [b, id] : qq[u]) {
    auto [x, y] = sgt.t[1];
    res[id] = std::max({res[id], t1.getdis(x, u) + t2.getdis(x, b), t1.getdis(y, u) + t2.getdis(y, b)});
  }
  for (auto [v, w] : t1.G[u]) {
    if (v == fa) continue;
    pos = v, sgt.update(1, 1, n, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1);
    dfs(v, u);
    pos = u, sgt.update(1, 1, n, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1);
  }
}

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    t1.add(u, v, w);
  }
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    t2.add(u, v, w);
  }
  for (int i = 1; i <= q; ++i) {
    int a, b;
    std::cin >> a >> b;
    qq[a].emplace_back(b, i);
  }
  t1.prework(), t2.prework();
  pos = 1, sgt.build(1, 1, n);
  dfs(1, 0);
  for (int i = 1; i <= q; ++i) std::cout << res[i] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}