题面

一棵以

1 为根的

N 个节点的有根树，

Q 次询问，每次问一个点

u 的

k 级兄弟有多少个（第

k 代祖先的第

k 代孩子），如果没有则输出 0 。

≤

N,Q\leq 10^6

N,Q≤106 。

题解

像这种一个 log 可过的题目就是拿来 O(n) 做的

狗狗有言：挺板的长链剖分。

我们用离线+长链剖分来解决第

k 代孩子的问题，每个链顶存一个数组，表示每一代孩子的个数，把轻儿子的链合并。这个是长链剖分的常有操作，总共复杂度

(

)

O(n)

O(n) 。

如何

(

)

O(1)

O(1) 找

k 级祖先，这个很简单，不必用倍增。只需要把询问挂到树上，然后

\rm dfs

dfs 临时用一个数组栈存祖先就行了。

CODE

唉，又水了一篇

全程不用 vector ，常数极小

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 1000005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

const int MOD = 1000000007;

int n,m,s,o,k;

int hd[MAXN],v[MAXN],nx[MAXN],cnt;

void ins(int x,int y) {

	v[++ cnt] = y; nx[cnt] = hd[x];

	hd[x] = cnt; return ;

}

int d[MAXN],le[MAXN],son[MAXN];

int hd2[MAXN],nx2[MAXN];

int U[MAXN],kk[MAXN],fa[MAXN],as[MAXN];

int st[MAXN],tp;

int ar[MAXN<<1],he[MAXN],CN;

void dfs0(int x,int ff) {

	d[x] = d[ff] + 1;

	st[++ tp] = x;

	for(int i = hd2[x];i;i = nx2[i]) {

		if(kk[i] >= d[x]) fa[i] = 0;

		else fa[i] = st[tp-kk[i]];

	}

	hd2[x] = 0;

	for(int i = hd[x];i;i = nx[i]) {

		dfs0(v[i],x);

		le[x] = max(le[x],le[v[i]] + 1);

		if(le[v[i]] >= le[son[x]]) son[x] = v[i];

	}

	tp --;

	return ;

}

void dfs(int x,int ff) {

	he[x] = ++ CN;

	ar[he[x]] ++;

	if(son[x]) dfs(son[x],x);

	for(int i = hd[x];i;i = nx[i]) {

		if(v[i] != son[x]) {

			dfs(v[i],x);

			for(int j = 0;j <= le[v[i]];j ++) {

				ar[he[x]+j+1] += ar[he[v[i]]+j];

			}

		}

	}

	for(int i = hd2[x];i;i = nx2[i]) {

		int le = d[U[i]] - d[x];

		as[i] = ar[he[x]+le] - 1;

	}

	return ;

}

int main() {

	n = read();m = read();

	for(int i = 2;i <= n;i ++) {

		s = read();o = i;

		ins(s,o);

	}

	for(int i = 1;i <= m;i ++) {

		U[i] = s = read();kk[i] = read();

		nx2[i] = hd2[s]; hd2[s] = i;

	}

	dfs0(1,0);

	for(int i = 1;i <= m;i ++) {

		if(!fa[i]) continue;

		nx2[i] = hd2[fa[i]]; hd2[fa[i]] = i;

	}

	dfs(1,0);

	for(int i = 1;i <= m;i ++) {

		putnum(as[i]);

		if(i < m) putchar(' ');

	}ENDL;

	return 0;

}

巴特西

P5384[Cnoi2019]雪松果树（长链剖分）

题面

题解

CODE

最新文章

热门文章

巴特西

P5384[Cnoi2019]雪松果树 （长链剖分）

题面

题解

CODE

最新文章

热门文章

P5384[Cnoi2019]雪松果树（长链剖分）