单独腾一篇博客吧!

关于树上k级祖先和树上k级儿子的绝对快做法

首先枚举下各种做法吧!

树上k级祖先

$O(nlogn)$预处理

1. 倍增求k级祖先

显然,回答一组询问也是严格log的

访问空间太慢而且会被卡空间所以很屑

2. 树剖求k级祖先

当重链长度大于k,我们k级祖先就在这条链上,对于一个链都记录了直接访问即可...

这个显然不如:

3. 长链剖分求k级祖先

预处理每个长链数组还是要的

预处理倍增数组还是要的QAQ否则你可以尝试OnO1rmq!

然后你会发现我们如果一步跳到k最高二进制位的祖先后

由于k级祖先的长链长度一定大于这个数的

所以我们可以再从那个点向上或者向下沿着长链跳一步即可

时间复杂度回答起来是O1的

O(n)离线

开一个栈记录从根到x dfs经过的所有点

然后我们考虑dfs到x回答x的所有询问即可

k级儿子个数和

hh

1. 线段树合并

按照深度为下标建树然后每个位置记录有多少数

线段树合并

2. dsu on tree

树上启发式合并

线段树合并另一种实现形式....

3. 离线树状数组

相当于数一个区间的某一个深度的个数

4. 二分+vector

每个深度的点开一个vector全部记录下来,然后在哪个vector处二分即可

当然可以压成所有的一个数组来优化空间

5. 长链剖分

$O(n)!$

出现了线性做法!

其实是利用了长链性质优化了dsu on tree

Finally

my choice : (你谷最快)

可以离线求k级祖先

然后第二个数点我们可以树上差分

因为只求等于某个数的个数啊...

附上你谷rank 1代码

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
const int MAXQ=3e6+7;
int n,m;
int ccnt,home[MAXN],id[MAXQ],nxt[MAXQ],to[MAXQ],fst[MAXN],sec[MAXN],dep[MAXN];
int ans[MAXN],st[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<21)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}

	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
	int _C=-1,_Z;
	char _sr[1<<21],_z[20];
	inline void Ot() {
		fwrite(_sr,1,_C+1,stdout),_C=-1;
	}
	inline void print(int x) {
		if(_C>1<<20)Ot();
		while(_z[++_Z]=x%10+48,x/=10);
		while(_sr[++_C]=_z[_Z],--_Z);
		_sr[++_C]=' ';
	}
}
using namespace fastIO;

inline void ct(const int &u,const int &v) {
	ccnt++;
	nxt[ccnt]=home[u];
	home[u]=ccnt;
	to[ccnt]=v;
}

inline void ct2(const int &u,const int &v,const int &z) {
	ccnt++;
	nxt[ccnt]=fst[u];
	fst[u]=ccnt;
	to[ccnt]=v;
	id[ccnt]=z;
}

inline void ct3(const int &u,const int &v,const int &z) {
	ccnt++;
	nxt[ccnt]=sec[u];
	sec[u]=ccnt;
	to[ccnt]=v;
	id[ccnt]=z;
}

int tp,cnt[MAXN];
inline void dfs(int u) {
	st[++tp]=u;
	int v;
	for(int i=fst[u]; i; i=nxt[i]) {
		v=to[i];
		if(v<tp) {
			ct3(st[tp-v],v,id[i]);
		}
	}
	for(int i=home[u]; i; i=nxt[i]) {
		v=to[i];
		dep[v]=dep[u]+1;
		dfs(v);
	}
	--tp;
}

inline void dfs2(int u) {
	int v;
	cnt[dep[u]]++;
	for(int i=sec[u]; i; i=nxt[i]) {
		v=to[i];
		ans[id[i]]-=cnt[dep[u]+v];
	}
	for(int i=home[u]; i; i=nxt[i]) {
		v=to[i];
		dfs2(v);
	}
	for(int i=sec[u]; i; i=nxt[i]) {
		v=to[i];
		ans[id[i]]+=cnt[dep[u]+v]-1;
	}
}

int main() {
//	freopen("test.in","r",stdin);
	n=read();
	m=read();
	for(int i=2,x; i<=n; ++i) {
		x=read();
		ct(x,i);
	}
	for(int i=1,x,y; i<=m; ++i) {
		x=read();
		y=read();
		ct2(x,y,i);
	}
	dep[1]=1;
	dfs(1);
	dfs2(1);
	for(int i=1; i<=m; ++i)print(ans[i]);
	Ot();
	return 0;
}