「IOI2009」Regions - 树链分块 / 大小分类

题目大意

    $N$个节点的树，有$R$种属性，每个点属于一种属性。有$Q$次询问，每次询问$r_1,r_2$，回答有多少对$(e_1,e_2)$满足$e_1$属性是$r_1$，$e_2$属性是$r_2$，$e_1$是$e_2$的祖先。

---

题目分析

本题可使用树链分块+关键点虚树的方法解决，但不好懂（achen：这不科学），可以参考neither_nor大佬的题解。
bzoj的良心内存使我成功MLE，不想管了。

考虑本题有两种暴力方法：

• 固定其中一种颜色，通过统计子树或路径信息得到与另一种颜色的答案。如固定颜色$r_1$，统计出每个颜色的点到根路径上的$r_1$颜色的个数，即可得到答案（统计子树类似）。预处理时间复杂度$O(n^2)$，空间复杂度$O(n^2)$，$O(1)$回答询问。
• 预处理出每种颜色的结点在树上的Dfs序，假设询问$(r_1,r_2)$中$r_1$颜色出现次数为$A$，$r_2$为$B$，则可以用$O(A+B)$的时间将它们合并起来。用栈维护子树关系，扫描一遍即可得出答案。预处理时间复杂度$O(n)$，空间复杂度$O(n)$，$O(A+B)$回答询问。

不难发现我们可以设定一定阈值使得两种暴力时间复杂度平衡。对于颜色数量$\gt\sqrt n$的颜色用第一种暴力统计，对于颜色数量$\le\sqrt n$的使用第二种暴力统计，这样时间复杂度就是$O(n\sqrt n)$了，空间复杂度$O(m\sqrt n)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=200005,maxm=25005,maxb=455;

int n,m,q,step=0,S[maxn],Hash[maxm],Color[maxn],First[maxn],Last[maxn];
LL Up[maxm][maxb],Down[maxm][maxb];
vector<int>Col[maxm],edges[maxn];

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Dfs(int Now) {
	First[Now]=++step;
	Col[Color[Now]].push_back(Now);
	for(int Next:edges[Now])Dfs(Next);
	Last[Now]=step;
}

int Solve(int Now,int col,int times) {
	if(Color[Now]==col)times++;
	else Up[Color[Now]][Hash[col]]+=times;
	int tmp=0;
	if(Color[Now]==col)tmp++;
	for(int Next:edges[Now])tmp+=Solve(Next,col,times);
	if(Color[Now]!=col)Down[Color[Now]][Hash[col]]+=tmp;
	return tmp;
}

bool cmp(int a,int b) {
	return First[a]<First[b];
}

LL Query(int x,int y) {
	if(Hash[x])return Up[y][Hash[x]];
	if(Hash[y])return Down[x][Hash[y]];
	vector<int>p;
	p.resize(Col[x].size()+Col[y].size());
	merge(Col[x].begin(),Col[x].end(),Col[y].begin(),Col[y].end(),p.begin(),cmp);
	int top=0,tot=0;
	LL ans=0;
	for(int now:p) {
		while(top>0&&(First[now]<First[S[top]]||Last[now]>Last[S[top]])) {
			tot-=Color[S[top]]==x;
			top--;
		}
		ans+=tot*(Color[now]==y);
		S[++top]=now;
		tot+=Color[now]==x;
	}
	return ans;
}

int main() {
	n=Get_Int();
	m=Get_Int();
	q=Get_Int();
	Color[1]=Get_Int();
	for(int i=2; i<=n; i++) {
		AddEdge(Get_Int(),i);
		Color[i]=Get_Int();
	}
	Dfs(1);
	int size=sqrt(n),BCC=0;
	for(int i=1; i<=m; i++)
		if(Col[i].size()>size) {
			Hash[i]=++BCC;
			Solve(1,i,0);
		}
	for(int i=1; i<=q; i++) {
		int x=Get_Int(),y=Get_Int();
		printf("%lld\n",Query(x,y));
	}
	return 0;
}