「IOI2009」Regions - 树链分块 / 大小分类 | Bill Yang's Blog

「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)$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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;
}
姥爷们赏瓶冰阔落吧~
0%