CF208E Blood Cousins(DSU，倍增)

倍增求出祖先，\(\text{DSU}\)统计

本来想用树剖求\(K\)祖，来条链复杂度就假了

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <numeric>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define MP make_pair

#ifdef QWQ

#define D_e_Line printf("\n------\n")

#define D_e(x) cerr << (#x) << " " << x << endl

#define C_e(x) cout << (#x) << " " << x << endl

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define Pause() system("pause")

#include <cassert>

#define PASS fprintf(stderr, "Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)

#else

#define D_e_Line

#define D_e(x)

#define C_e(x)

#define FileOpen()

#define FileSave()

#define Pause()

#define PASS

#endif

using namespace std;

struct FastIO {

	template<typename ATP> inline FastIO& operator >> (ATP &x) {

		x = 0; int sign = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') sign = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		if(sign == -1) x = -x;

		return *this;

	}

} io;

template<typename ATP> inline ATP Max(ATP x, ATP y) {

	return x > y ? x : y;

}

template<typename ATP> inline ATP Min(ATP x, ATP y) {

	return x < y ? x : y;

}

template<typename ATP> inline ATP Abs(ATP x) {

	return x < 0 ? -x : x;

}

#include <vector>

const int N = 1e5 + 7;

struct Edge {

	int nxt, pre;

} e[N];

int head[N], cntEdge;

inline void add(int u, int v) {

	e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;

}

vector<pair<int, int>> q[N];

int dep[N], fa[N][19], siz[N], top[N], dfn[N], dfnIdx, rnk[N], son[N];

void DFS_First(int u, int father) {

	dep[u] = dep[father] + 1, fa[u][0] = father, siz[u] = 1;

	R(i,1,18){

		if(fa[u][i - 1]) fa[u][i] = fa[fa[u][i - 1]][i - 1];

		else break;

	}

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		DFS_First(v, u);

		siz[u] += siz[v];

		if(siz[v] > siz[son[u]]) son[u] = v;

	}

}

void DFS_Second(int u, int Tp) {

	top[u] = Tp, dfn[u] = ++dfnIdx, rnk[dfnIdx] = u;

	if(!son[u]) return;

	DFS_Second(son[u], Tp);

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(v != son[u]) DFS_Second(v, v);

	}

}

inline int Father(int u, int K) {

//	while(dep[u] - dep[top[u]] + 1 <= K){

//		K -= dep[u] - dep[top[u]] + 1;

//		u = fa[top[u]];

//	}

//	return rnk[dfn[u] - K];

	while(K){

		int now = 0;

		while((1 << (now + 1)) <= K) ++now;

		u = fa[u][now];

		K -= 1 << now;

	}

	return u;

}

int tot[N];

bool big[N];

void Add(int u) {

	++tot[dep[u]];

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(big[v]) continue;

		Add(v);

	}

}

void Del(int u) {

	--tot[dep[u]];

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(big[v]) continue;

		Del(v);

	}

}

int ans[N], n;

void DSU(int u, bool flag) {

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(v == son[u]) continue;

		DSU(v, 0);

	}

	if(son[u]) DSU(son[u], 1), big[son[u]] = true;

	Add(u);

	for(vector<pair<int, int>>::iterator it = q[u].begin(); it != q[u].end(); ++it){

		if(it->first + dep[u] <= n + 1){

			ans[it->second] = tot[it->first + dep[u]] - 1;

		}

	}

	big[son[u]] = false;

	if(!flag) Del(u);

}

int main() {

	int Q;

	io >> n;

	R(i,1,n){

		int fat;

		io >> fat;

		++fat;

		add(fat, i + 1);

	}

	DFS_First(1, 0);

	DFS_Second(1, 1);

//	while(1){

//		int x, K;

//		io >> x >> K;

//		++x;

//		cout << Father(x, K) - 1<< endl;

//	}

	io >> Q;

	R(i,1,Q){

		int x, K;

		io >> x >> K;

		++x;

		x = Father(x, K);

		if(x == 1){

			continue;

		}

//		D_e(x - 1);

		q[x].emplace_back(K, i);

	}

	DSU(1, 0);

	R(i,1,Q){

		printf("%d ", ans[i]);

	}

	return 0;

}

/*

6

0 1 1 0 4 4

7

1 1

1 2

2 1

2 2

4 1

5 1

6 1

*/

/*

6

0 1 2 3 4 5

5 1

*/

CF208E Blood Cousins(DSU，倍增)的相关教程结束。