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

#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;
}