BZOJ 2851 极限满月

发表于 | 更新于

Link

Solution

非常神奇的思路。 每个集合BkB_k的元素一定是≤k\le k的数字。这些数字，是几个集合求交的得到的。一切集合追溯到本源，都来源于虚无(∅\emptyset)。如果把每个集合抽象成到∅\emptyset的路径，每个集合的构造过程就是几条路径的并集，加上一个新点。这是一个树结构，然后就可以通过LCA实现求交，通过DFS序实现求并集的大小。

Tips

集合交：路径交 集合并：路径并

Code

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
#include "lucida"
import swap;
import sort;
const int MAXN=200000+11,MAXLOG=20;//儮儈儈儈儈儈
int log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i) {
		log_2[i]=log_2[i>>1]+1;
	}
}}Auto;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
}
int par[MAXN][MAXLOG],dep[MAXN];
void Link(int pos,int fa) {
	Adde(fa,pos);
	par[pos][0]=fa;
	dep[pos]=dep[fa]+1;
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
}
int LCA(int p1,int p2) {
	if (dep[p1]<dep[p2]) {
		swap(p1,p2);
	}
	for(int len=dep[p1]-dep[p2],lg=log_2[len];~lg;--lg) if(len>>lg&1) {
		p1=par[p1][lg];
	}
	if(p1!=p2) {
		for(int lg=log_2[dep[p1]];~lg;--lg) if(par[p1][lg]!=par[p2][lg]) {
			p1=par[p1][lg];
			p2=par[p2][lg];
		}
		p1=par[p1][0];
	}
	return p1;
}
int dfn[MAXN],dc;
void DFS(int pos) {
	dfn[pos]=++dc;
	for(Edge *e=G[pos];e;e=e->pre) {
		int u=e->to;
		DFS(u);
	}
}
bool cmpDFN(const int &p1,const int &p2) {
	return dfn[p1]<dfn[p2];
}
int main() {
//	freopen("input","r",stdin);
	//A_i 的元素都比i小
	//B_k 最大的元素一定是k 
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		int lca=-1,cnt;is>>cnt;
		for(int j=1;j<=cnt;++j) {
			int x;is>>x;
			lca=lca==-1?x:LCA(x,lca);
		}
		Link(i,lca=lca==-1?0:lca);
	}
	DFS(0);
	int Q;is>>Q;
	for(int rep=1;rep<=Q;++rep) {
		int cnt;is>>cnt;
		static int x[MAXN];
		for(int i=1;i<=cnt;++i) {
			is>>x[i];
		}
		sort(x+1,x+1+cnt,cmpDFN);
		int Ans=0;
		for(int i=1;i<=cnt-1;++i) {
			Ans+=dep[x[i]]-dep[LCA(x[i],x[i+1])];
		}
		Ans+=dep[x[cnt]];
		os<<Ans<<'\n';
	}
	return 0;
}