Codeforces Round 130 (Div. 2) E. Blood Cousins（LCA+DFS序+二分）【2100】

题目链接

https://codeforces.com/contest/208/problem/E

思路

此题有两个要点：第一，快速找到节点$u$的$p$级祖先。第二，在以节点$u$为根的子树中找到与节点$u$深度相同的节点的个数。

对于第一点，我们可以使用LCA算法在树上倍增，实现快速查询。

对于第二点，我们可以按照深度，将所有节点的DFS序全部存储到vector中，因为DFS序的单调性，直接二分查找即可。

时间复杂度：$O(nlo{g}_{2}n)$

代码

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long doubletypedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;const int N = 1e5 + 5, M = 1e2 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;std::mt19937 rnd(time(0));int n, m;
int r[N];
struct LCA
{vector<vector<int>>mp;vector<int>depth;vector<int>L, R;vector<vector<int>>fa;vector<vector<int>>dep;int idx;LCA() {}LCA(int n) {init(n);}void init(int n){mp.resize(n + 1);depth.resize(n + 1);L.resize(n + 1), R.resize(n + 1);fa.resize(n + 1, vector<int>(20));dep.resize(n + 1);idx = 0;fill(depth.begin(), depth.end(), inf);}void add_edge(int a, int b){//建双向边mp[a].push_back(b);mp[b].push_back(a);}void dfs(int u, int fu){L[u] = ++idx;dep[depth[u]].push_back(L[u]);for (int j : mp[u]){if (j == fu) continue;dfs(j, u);}R[u] = idx;}void bfs(int root){depth[0] = 0, depth[root] = 1;queue<int>q;q.push(root);while (q.size()){int u = q.front();q.pop();for (int i = 0; i < mp[u].size(); i++){int j = mp[u][i];if (depth[j] > depth[u] + 1){depth[j] = depth[u] + 1;q.push(j);fa[j][0] = u;for (int k = 1; k <= 19; k++){fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}}int lca(int a, int b){if (depth[a] < depth[b]) swap(a, b);for (int k = 19; k >= 0; k -- )if (depth[fa[a][k]] >= depth[b])a = fa[a][k];if (a == b) return a;for (int k = 19; k >= 0; k -- )if (fa[a][k] != fa[b][k]){a = fa[a][k];b = fa[b][k];}return fa[a][0];}int find(int u, int len){for (int k = 19; k >= 0; k--){int res = 1ll << k;if (res <= len){len -= res;u = fa[u][k];}}return u;}
};
void solve()
{cin >> n;LCA tree(n);for (int i = 1; i <= n; i++){cin >> r[i];if (r[i]) tree.add_edge(i, r[i]);}for (int i = 1; i <= n; i++){if (!r[i])tree.bfs(i);}for (int i = 1; i <= n; i++){if (!r[i])tree.dfs(i, 0);}cin >> m;while (m--){int u, p;cin >> u >> p;if (tree.depth[u] <= p){cout << 0 << " ";}else{int zu = tree.find(u, p);int deep = tree.depth[u];int low = lower_bound(tree.dep[deep].begin(), tree.dep[deep].end(), tree.L[zu]) - tree.dep[deep].begin();int high = upper_bound(tree.dep[deep].begin(), tree.dep[deep].end(), tree.R[zu]) - tree.dep[deep].begin();high--;cout << high - low + 1 - 1 << " ";}}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}