给定 $n$ 个点的树,上有 $m$ 条链,每次询问给定一个路径,查询至少需要多少条链能把这条路径完全覆盖。

考虑将路径拆分为从两个节点跳到根节点的路径,倍增维护跳 $2^i$ 步能够到达的最高节点,跳到离根节点最近的两个节点 $x$ 和 $y$,需要查询这两个节点是否有一条链覆盖。当我们递归搜索到 $x$ 时,我们记录在 $y$ 子树内链终点的个数,然后将 $x$ 子树内所有链全都加入到数据结构中,再次查询 $y$ 子树内链终点的个数,若增加,则存在链覆盖 $(x,y)$。

#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
  x = 0; 
  int c = 0, f = 0;
  for (; !isdigit(c); c = getchar()) 
    f |= c == '-';
  for (; isdigit(c); c = getchar()) 
    x = x * 10 + (c & 15);
  x = f ? -x : x;
}

const int N = 2e5 + 5;

struct edge {
  int to, nxt;
} e[N];

int head[N];
int edge_cnt;

void add_edge(int u, int v) {
  e[++edge_cnt] = (edge){v, head[u]};
  head[u] = edge_cnt;
}

int dep[N], fa[N];
int dfn_in[N], dfn_out[N];
int bz[23][N], climb[23][N];
int dfc; 
int n, m, q;
bool flag[N];
int ans[N], tag[N];
vector<int> _end[N];
vector<pair<int, int>> qry[N];

void Dfs(int u) {
  dfn_in[u] = ++dfc;
  dep[u] = dep[fa[u]] + 1; 
  bz[0][u] = fa[u];
  for (int i = 1; i <= 22; ++i) 
    bz[i][u] = bz[i - 1][bz[i - 1][u]]; 
  for (int i = head[u]; i; i = e[i].nxt) 
    Dfs(e[i].to); 
  dfn_out[u] = dfc;
}

void Dfs_2(int u) {
  for (int i = head[u]; i; i = e[i].nxt) {
    Dfs_2(e[i].to); 
    if (!climb[0][u] || dep[climb[0][e[i].to]] < dep[climb[0][u]])
      climb[0][u] = climb[0][e[i].to];
  }  
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) 
    swap(x, y); 
  for (int i = 22; i >= 0; --i) 
    if (dep[bz[i][x]] >= dep[y]) 
      x = bz[i][x]; 
  if (x == y) 
    return x; 
  for (int i = 22; i >= 0; --i) 
    if (bz[i][x] != bz[i][y]) 
      x = bz[i][x], y = bz[i][y]; 
  return fa[x]; 
}

bool reach(int x, int y) {
  return dfn_in[climb[22][x]] <= dfn_in[y] && dfn_out[y] <= dfn_out[climb[22][x]]; 
}

pair<int, int> climb_up(int x, int y) {
  int cost = 0; 
  for (int i = 22; i >= 0; --i) {
    if (dep[climb[i][x]] > dep[y]) {
      cost += (1 << i); 
      x = climb[i][x]; 
    }
  }
  return make_pair(x, cost); 
}

struct Fenwick {
  int n; 
  int fw[N];
  
  void init(int x) {
    n = x; 
    memset(fw, 0, sizeof fw); 
  }
  
  void modify(int pos, int v) {
    for (; pos <= n; pos += pos & -pos) 
      fw[pos] += v; 
  }
  
  int query(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos) 
      res += fw[pos];
    return res; 
  }
  
  int query_sec(int l, int r) {
    return query(r) - query(l - 1); 
  }
} bit;

void solve(int u) {
  for (auto v : qry[u]) 
    tag[v.second] -= bit.query_sec(dfn_in[v.first], dfn_out[v.first]);
  for (auto i : _end[u]) 
    bit.modify(dfn_in[i], 1);
  for (int i = head[u]; i; i = e[i].nxt) 
    solve(e[i].to); 
  for (auto v : qry[u]) {
    tag[v.second] += bit.query_sec(dfn_in[v.first], dfn_out[v.first]);
    if (tag[v.second] > 0) {
      --ans[v.second];
    }
  }
}

int main() {
  read(n); 
  for (int i = 2; i <= n; ++i) {
    read(fa[i]); 
    add_edge(fa[i], i); 
  }
  Dfs(1); 
  read(m);
  for (int i = 1; i <= n; ++i)
    climb[0][i] = i; 
  for (int i = 1, u, v; i <= m; ++i) {
    read(u), read(v); 
    int _lca = lca(u, v); 
    if (dep[climb[0][u]] > dep[_lca]) 
      climb[0][u] = _lca; 
    if (dep[climb[0][v]] > dep[_lca]) 
      climb[0][v] = _lca;
    _end[u].emplace_back(v); 
    _end[v].emplace_back(u); 
  }
  Dfs_2(1); 
  for (int i = 1; i <= 22; ++i) 
    for (int j = 1; j <= n; ++j) 
      climb[i][j] = climb[i - 1][climb[i - 1][j]]; 
  read(q);
  for (int i = 1, u, v; i <= q; ++i) {
    read(u), read(v); 
    int _lca = lca(u, v);
    if (!reach(u, _lca) || !reach(v, _lca)) {
      flag[i] = 1; 
      continue;
    }
    pair<int, int> a = climb_up(u, _lca), b = climb_up(v, _lca); 
    ans[i] = a.second + b.second;
    if (a.first != _lca && b.first != _lca) 
      qry[a.first].emplace_back(b.first, i); 
    if (b.first != _lca) 
      ++ans[i];
    if (a.first != _lca) 
      ++ans[i]; 
  }
  bit.init(n);
  solve(1);
  for (int i = 1; i <= q; ++i) 
    if (flag[i]) 
      printf("-1\n"); 
    else 
      printf("%d\n", ans[i]);
  return 0; 
}
最后修改:2020 年 08 月 23 日 09 : 54 PM
如果觉得我的文章对你有用,请随意赞赏