Blood Cousins (dsu on tree + 求第k級祖先)

題目連結: Blood Cousins

大緻題意

給出一片森林, 詢問對于給定的點而言, 其k級祖先中有多少個點的深度和目前節點相同.

解題思路

dsu on tree

對于每個詢問

x, k

而言, 我們假設x的k級祖先為p, 則對于每一個p, 我們求出其子樹中不同深度的節點數量即可. 我們可以通過dsu on tree做法求出.

關于節點的k級祖先求法, 大家可以看這篇部落格 ➡️ 部落格連結

AC代碼

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
vector<int> edge[N];

int son[N], sz[N];
int depth[N], f[N][18];
void dfs1(int x, int fa) {
	depth[x] = depth[fa] + 1;
	sz[x] = 1;

	f[x][0] = fa;
	rep(i, 17) f[x][i] = f[f[x][i - 1]][i - 1];

	for (auto& to : edge[x]) {
		if (to == fa) continue;
		dfs1(to, x);
		sz[x] += sz[to];
		if (sz[to] > sz[son[x]]) son[x] = to;
	}
}

int getk(int x, int k) {
	if (!k) return x;
	int index = log2(k);
	return getk(f[x][index], k - (1 << index));
}

vector<pair<int, int>> query[N]; // val, id
int res[N];
unordered_map<int, int> mp; // depth, cou;
void calc(int x, int fa, int pson) {
	mp[depth[x]]++;
	for (auto& to : edge[x]) {
		if (to == fa or to == pson) continue;
		calc(to, x, pson);
	}
}
void dfs2(int x, int fa, int tp) {
	for (auto& to : edge[x]) {
		if (to == fa or to == son[x]) continue;
		dfs2(to, x, 0);
	}

	if (son[x]) dfs2(son[x], x, 1);
	calc(x, fa, son[x]);

	for (auto& [val, id] : query[x]) res[id] = mp[val] - 1;

	if (!tp) mp.clear();
}
int main()
{
	int n; cin >> n;
	rep(i, n) {
		int p; scanf("%d", &p);
		edge[p].push_back(i);
	}
	for (auto& op : edge[0]) dfs1(op, 0);

	int m; cin >> m;
	rep(i, m) {
		int x, k; scanf("%d %d", &x, &k);
		int p = getk(x, k);
		query[p].push_back({ k + depth[p], i }); //采用相對于根節點的深度.
	}

	for (auto& op : edge[0]) dfs2(op, 0, 0); //由于是森林, 是以根節點應為輕兒子, 否則WA9

	rep(i, m) printf("%d%c", res[i], " \n"[i == m]);
	return 0;
}
           

END