【线段树合并】Codeforces Round 279 (Div. 2) F. Treeland Tour (树上最长上升子序列)
2021-08-15 16:17:00 # ACM

题链

题意如题

权值线段树维护
以 x 为结尾的最长上升子序列的长度
以 x 为开头的最长下降子序列的长度
一开始所有的 lis, lds 都是 1
dfs 到叶子节点然后自底向上维护每个节点的权值线段树

考虑某一棵子树，答案由两部分组成：
 经过根节点 u 的子序列：
  1. 左子树中小于 w[u] 的最长上升子序列长度
   +右子树中大于 w[u] 的最长下降子序列长度+1
  2. 左子树中大于 w[u] 的最长下降子序列长度
   +右子树中大于 w[u] 的最长上升子序列长度+1
 不经过根节点 u 的子序列：
  需要在子树线段树合并的时候考虑

复杂度O(nlogn)

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
	#define Pair pair<int ,int >
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 1000001
	#define MS 100005

int n,m;
int w[MS];
vector<int > vc[MS];
struct node{
	int l,r;
	int lis,lds;
}p[MS*30];
int rtpos[MS], tot;
int ans;

Pair pmax(Pair t1,Pair t2){
	return { max(t1.first ,t2.first )
		   , max(t1.second,t2.second) };
}

Pair query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return {p[rt].lis,p[rt].lds};
	}
	int m = l+r>>1;
	Pair ans = {0,0};
	if(m >= L) ans = pmax(ans, query(L,R,l,m,p[rt].l) );
	if(m <  R) ans = pmax(ans, query(L,R,m+1,r,p[rt].r) );
	return ans;
}

void push_up(int rt){
	p[rt].lis = max(p[p[rt].l].lis,p[p[rt].r].lis);
	p[rt].lds = max(p[p[rt].l].lds,p[p[rt].r].lds);
}

void modify(int pos,int l,int r,int &rt,int vlis,int vlds){
	if(!rt) rt = ++tot;
	if(l == r){
		p[rt].lis = max(p[rt].lis, vlis);
		p[rt].lds = max(p[rt].lds, vlds);
		return;
	}
	int m = l+r>>1;
	if(m >= pos) modify(pos,l,m,p[rt].l,vlis,vlds);
	else modify(pos,m+1,r,p[rt].r,vlis,vlds);
	push_up(rt);
}

void merge(int &x,int y,int l,int r){
	if(!x || !y) x |= y;
	else if(l == r){
		p[x].lis = max(p[x].lis,p[y].lis);
		p[x].lds = max(p[x].lds,p[y].lds);
	}
	else{
		// 答案可能来自不经过根节点的最长上升子序列 
		ans = max(ans, max(p[p[x].l].lis + p[p[y].r].lds
						  ,p[p[x].r].lds + p[p[y].l].lis) );
		// 递归合并左右子树 
		int m = l+r>>1;
		merge(p[x].l,p[y].l,l,m);
		merge(p[x].r,p[y].r,m+1,r);
		push_up(x);
	}
}

void dfs(int u,int f){
	int nlis = 0, nlds = 0;
	for(auto v:vc[u]){
		if(v != f){
			dfs(v,u);
			// u为某子树根节点 
			// 这里计算经过点 u 的 lis和 lds 
			// 得到子树中权值小于 w[u]的 lis, 权值大于 w[u]的 lds 
			int tlis = query(0,w[u]-1,0,MAXN,rtpos[v]).first;
			int tlds = query(w[u]+1,MAXN,0,MAXN,rtpos[v]).second;
			// 更新答案 
			ans = max(ans, max( tlis+nlds+1, tlds+nlis+1 ));
			// 更新点 u 为结尾的 lis,lds 
			nlis = max(nlis,tlis);
			nlds = max(nlds,tlds);
			// 将 v合并至 u 
			merge(rtpos[u],rtpos[v],0,MAXN);
		}
	}
	// 更新 u的权值线段树 
	modify(w[u],0,MAXN,rtpos[u],nlis+1,nlds+1);
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> w[i];
	for(int i=2;i<=n;i++){
		int u,v;
		cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u); 
	}
	dfs(1,0);
	cout << ans << "\n";
} 

int main() {
//	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/
Prev
2021-08-15 16:17:00 # ACM
Next