【重链剖分】The 15-th Beihang University Collegiate Programming Contest (BCPC 2020) - Final H、宝可梦与分支进化
2021-05-18 14:59:00 # ACM

题链

$dp[x]$ 表示以 $x$ 为进化终点能取得的最大进化次数；

可以发现 $dp[x]$ 等于 树上$x$的前缀最大值 $+1$;

但是不可能递归寻找$x$的父亲直到根节点，因为会超时；

所以采用重链剖分+线段树维护前缀最大值，复杂度$O(nlogn*logn)$；

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
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 500009

int n,m;
vector<int > vc[MS];
int fa[MS];
int sz[MS];
int dep[MS];
int zson[MS];
int tim;
int top[MS];
int dfn[MS];
int val[MS];
int p[MS<<2];

void dfs1(int u,int f){
	fa[u] = f;
	sz[u] = 1;
	dep[u] = dep[f]+1;
	zson[u] = 0;
	int maxn_zson = 0;
	for(auto &v:vc[u]){
		if(v == f) continue;
		dfs1(v,u);
		sz[u] += sz[v];
		if(sz[v] > maxn_zson){
			zson[u] = v;
			maxn_zson = sz[v];
		}
	}
} 

void dfs2(int u,int tp){
	dfn[u] = ++tim;
	top[u] = tp;
	val[tim] = 0;
	if(zson[u]) dfs2(zson[u],tp);
	for(auto &v:vc[u]){
		if(v == fa[u] || v == zson[u]) continue;
		dfs2(v,v);
	}
}

void update(int pos,int l,int r,int rt,int val){
	if(l == r){
		p[rt] = val;
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(pos,l,m,ls,val);
	if(m <  pos) update(pos,m+1,r,rs,val);
	p[rt] = max(p[ls],p[rs]);
}

int query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt];
	}
	int ans = 0;
	int m = l+r>>1;
	if(m >= L) ans = max(ans,query(L,R,l,m,ls));
	if(m <  R) ans = max(ans,query(L,R,m+1,r,rs));
	return ans;
}

int get_max(int x){
	if(x == fa[x]) return 0; // 如果是根节点则无前缀，返回 0 
	x = fa[x]; // 从x的父亲为起点，向上跳 
	int ans = query(dfn[x],dfn[x],1,n,1); // 初值为父亲的值 
	while(x != fa[x]){ // 一直跳到根节点 
		ans = max(ans, query(dfn[top[x]],dfn[x],1,n,1) );
		x = fa[top[x]];
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=2;i<=n;i++){
		int x;
		cin >> x;
		vc[x].push_back(i);
	}
	dfs1(1,1);
	dfs2(1,1);
	int ans = 0;
	for(int i=1;i<=m;i++){
		int x;
		cin >> x;
		int cc = get_max(x)+1; // 求 x 的前缀最大值（不含 x ） 
		update(dfn[x],1,n,1,cc);
		ans = max(ans,cc);
	}
	cout << ans << "\n";
	
	
	return 0;
}
Prev
2021-05-18 14:59:00 # ACM
Next