题解：P9246 [蓝桥杯 2023 省 B] 砍树

· · 题解

挺有意思的一题，目前还没有题解，写一个简要的题解吧。

树上任意两点之间的关键路径是唯一的且经过二者的 LCA。故切断两点之间的通路就是要在这条唯一的路径之上任意选择一条边进行切断。题中有多对点需要满足不连通条件，那么可行的断边方案就是每对点可行的断边方案的交集。考虑统计在题中 m 条不连通点对约束下，每条边作为可行解的总次数，如果该次数等于 m，则该条边属于最终的可行解集，反之亦然。

计算 LCA 可以使用倍增或树剖（O(n\log n)）或 O(n) 离线算法，统计次数（求交集）可以在树剖后使用树状数组/线段树（O(m\log^2n)），或使用树上差分（O(n)，不依赖于具体的 LCA 方案）。本题解以 树剖 + 树状数组 方案为例。

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<pair<int, int>>> neigh;
vector<int> eid, depth, parent, child, nmemb, id, head;

template<class T>
void reorder(vector<T> &v)
{
  int nv = v.size();
  vector<T> u(nv);
  for(int i = 0; i < nv; ++i) swap(u[id[i]], v[i]);
  swap(v, u);
}

void renumber(vector<pair<int, int>> &v)
{
  for(auto &[i, ei] : v) {
    if(i >= 0) i = id[i];
  }
}

void renumber(vector<int> &v)
{
  for(int &i : v) {
    if(i >= 0) i = id[i];
  }
}

void renumber()
{
  reorder(neigh);
  for(auto &v : neigh) renumber(v);
  reorder(eid);
  reorder(depth);
  reorder(parent), renumber(parent);
  reorder(child), renumber(child);
  reorder(nmemb);
  reorder(head), renumber(head);
}

void build_tree(int i, int p)
{
  depth[i] = p < 0 ? 0 : depth[p] + 1;
  parent[i] = p;
  child[i] = -1;
  nmemb[i] = 1;
  for(auto [j, ei] : neigh[i]) {
    if(j == p) continue;
    eid[j] = ei;
    build_tree(j, i);
    if(child[i] < 0 || nmemb[child[i]] < nmemb[j]) child[i] = j;
    nmemb[i] += nmemb[j];
  }
}

void build_head(int i)
{
  static int seq;
  id[i] = seq++;
  head[i] = i;
  if(parent[i] >= 0 && i == child[parent[i]]) head[i] = head[parent[i]];
  if(child[i] >= 0) build_head(child[i]);
  for(auto [j, ei] : neigh[i]) {
    if(j == parent[i]) continue;
    if(j == child[i]) continue;
    build_head(j);
  }
}

class BIT {
public:
  BIT() { }
  BIT(int nv) { v.resize(nv + 1); }
  void Add(int i, int a)
  {
    for(++i; i <= n; i += (i & -i)) v[i] += a;
  }
  int Sum(int i) const
  {
    int s = 0;
    for(++i; i; i &= (i - 1)) s += v[i];
    return s;
  }

private:
  vector<int> v;
};

BIT bit;

void inc(int i, int j)
{
  bit.Add(i, 1);
  if(j + 1 < n) bit.Add(j + 1, -1);
}
int get(int i) { return bit.Sum(i); }

void mark_disconn(int u, int v)
{
  while(head[u] != head[v]) {
    if(depth[head[u]] >= depth[head[v]]) {
      inc(head[u], u);
      u = parent[head[u]];
    } else {
      inc(head[v], v);
      v = parent[head[v]];
    }
  }
  if(u == v) return;
  if(u > v) swap(u, v);  // u < v
  inc(u + 1, v);
}

int main()
{
  int m;
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;

  neigh.resize(n);
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v, --u, --v;
    neigh[u].emplace_back(v, i), neigh[v].emplace_back(u, i);
  }
  eid.resize(n), depth.resize(n), parent.resize(n), child.resize(n), nmemb.resize(n), id.resize(n), head.resize(n);
  build_tree(0, -1);
  build_head(0);
  renumber();

  bit = BIT(n);
  for(int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v, --u, --v, u = id[u], v = id[v];
    mark_disconn(u, v);
  }

  int ans = -1;
  for(int i = 1; i < n; ++i) {
    if(get(i) != m) continue;
    ans = max(ans, eid[i] + 1);
  }
  cout << ans << endl;
  return 0;
}

由于上面对数状数组的访问中修改和查询是完全分开的，故也可以直接使用普通数组替换。