2021 Jiangsu Collegiate Programming Contest F. Jumping Monkey II 树剖+线段树

F. Jumping Monkey II

题意：
给你$n=2e5$的一棵树，每个点有点权 $a[i]<=1e9$，对于每个点，求以这个点出发，并且以自己为 $LIS$ 的起点 的 最长 $LIS$的长度。

思路：
首先假设一号结点为根，然后每个点作为LIS的起点有三种可能：

标注$st$的结点为 $LIS$的起点，直线向上代表走父亲，向下代表走子树。
圆圈的点，是在 $LIS$上的点，不在 $LIS$上的点没有画出，用直线表示。

情况一：子树的结点做贡献
情况二：祖先结点和子树不做贡献，从除子树和祖先结点转移过来
情况三：祖先结点做贡献，从祖先结点转移过来

对于情况一，我们需要在子树里找点权比当前点大，且 向下的 $LIS$最长的 转移过来。
对于情况二，我们需要在除子树和除祖先结点里找点权比当前点大，且 向下的 $LIS$最长的 转移过来。
考虑这两个一起做，点权比当前点大的限制比较难处理，所以考虑按照点权从大到小加点，并用线段树维护。
对于情况一，就可以用 $dfs$序求子树 查询最大值转移过来。（为了下面的情况三，这里每个点需要求出向下的最大长度和次大长度，并且记一下最大长度是哪个子树转移过来的。）
对于情况二，就可以利用 树剖序 求不在当前向上的重链以及子树的 最大值转移过来。

现在只需要考虑情况三，可以发现每个祖先$fa$ 有 三种选择：
第一种： 从$fa$的祖先转移过来；
第二种：不从 $fa$的祖先且不从子树转移过来，即其他部分转移过来；
第三种: 从 $fa$的子树转移过来，但是子树不和当前 结点 $x$的子树重合；

然后每个点可以从祖先中点权比自己大的最大值转移过来。
这里就不能从大到小加点了，因为有子树不能重合的限制，考虑 $dfs$的过程中 用线段树维护 当前结点到根的路径上的信息。用排序过后的标号来建线段树，就可以用区间查询最大值 来实现 求点权比自己大的最大值了。

详细细节见代码。
只能说跑的飞快：

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define repp(i,n,m) for(int i=n;i>=m;i--)
const int N= 2e5+10;

int n,m,t;
vector<int>v[200050],vv;
struct nod{
	int x,id;
}z[200050];
int dfn[200050],siz[200050];
int len=0;


int tr[2][800050];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
int ans[200005];
int dep[200059],fa[200050],top[200050],son[200050];
int dp[200050][2],id[200050];
int idd[200050],st[200050],ed[200060];

void dfs1(int x,int pre){
	fa[x]=pre;dep[x]=dep[pre]+1;
	siz[x]=1;
	son[x]=0;
	for(auto to:v[x]){
		if(to==pre)continue;
		dfs1(to,x);
		siz[x]+=siz[to];
		if(siz[to]>=siz[son[x]])son[x]=to;
	}
}
void dfs2(int x,int pre){
	if(son[pre]==x)top[x]=top[pre];
	else top[x]=x;
	dfn[x]=++len;
	if(son[x])dfs2(son[x],x);
	for(auto to:v[x]){
		if(to==pre||to==son[x])continue;
		dfs2(to,x);
	}
}
bool cmp(nod a,nod b){
	return a.x>b.x;
}
void build(int p,int l,int r,int op){
	tr[op][p]=0;
	if(l==r)return;
	build(ls,l,mid,op);
	build(rs,mid+1,r,op);
}
void update(int p,int l,int r,int x,int w,int op){
	if(l==r){
		tr[op][p]=w;
		return;
	}
	if(x<=mid)update(ls,l,mid,x,w,op);
	else update(rs,mid+1,r,x,w,op);
	tr[op][p]=max(tr[op][ls],tr[op][rs]);
}
int query(int p,int l,int r,int x,int y,int op){
	if(x>y)return 0;
	if(x<=l&&r<=y){
		return tr[op][p];
	}
	int ans=0;
    if(x<=mid)ans=max(ans,query(ls,l,mid,x,y,op));
    if(mid<y)ans=max(ans,query(rs,mid+1,r,x,y,op));
    return ans;
}
void up(int x,int y){
	int i=y;
	while(top[x]!=top[y]){
		int a=top[y];
		int b=y;
				
		ans[i]=max(ans[i],query(1,1,n,dfn[b]+siz[b],dfn[a]+siz[a]-1,0)+1);
		y=fa[top[y]];
		ans[i]=max(ans[i],query(1,1,n,dfn[y]+1,dfn[a]-1,0)+1);
		ans[i]=max(ans[i],query(1,1,n,dfn[a]+siz[a],dfn[y]+siz[y]-1,0)+1);
	}
	int a=top[y];
	int b=y;
	ans[i]=max(ans[i],query(1,1,n,dfn[b]+siz[b],dfn[a]+siz[a]-1,0)+1);
}
void dfs3(int x,int pre){
	int res=query(1,1,n,1,st[z[idd[x]].x]-1,1)+1;
	ans[x]=max(ans[x],res);
	update(1,1,n,idd[x],max(res,max(ans[x],dp[x][1])),1);
	if(id[x]!=-1)dfs3(v[x][id[x]],x);
	update(1,1,n,idd[x],max(res,max(ans[x],dp[x][0])),1);
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		if(i==id[x]||to==pre)continue;
		dfs3(to,x);
	}
	update(1,1,n,idd[x],0,1);
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		len=0;
		vv.clear();
		for(int i=1;i<=n;i++){
			scanf("%d",&z[i].x);
			z[i].id=i;
			vv.push_back(z[i].x);
			ans[i]=0;
		}
		sort(vv.begin(),vv.end());
		vv.erase(unique(vv.begin(),vv.end()),vv.end());
		for(int i=1;i<=n;i++){
			z[i].x=lower_bound(vv.begin(),vv.end(),z[i].x)-vv.begin()+1; 
		}
		for(int i=1;i<n;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		build(1,1,n,0);
		build(1,1,n,1);
		dfs1(1,0);
		dfs2(1,0);
		sort(z+1,z+1+n,cmp);
		for(int i=1;i<=n;i++){
			if(z[i].x!=z[i-1].x)st[z[i].x]=i;
			ed[z[i].x]=i;
			idd[z[i].id]=i;
		}
		ll pre=1;
		rep(i,1,n){
			if(z[i].x!=z[pre].x){
				while(pre<i){
					update(1,1,n,dfn[z[pre].id],dp[z[pre].id][0],0);
					pre++;
				}
			}
			dp[z[i].id][0]=1;
			dp[z[i].id][1]=-1e9;
			id[z[i].id]=-1;
			int cnt=-1;
			for(auto to:v[z[i].id]){
				cnt++;
				if(to==fa[z[i].id])continue; 
				int res=query(1,1,n,dfn[to],dfn[to]+siz[to]-1,0);
				if(res+1>dp[z[i].id][0]){
					dp[z[i].id][1]=dp[z[i].id][0];
					dp[z[i].id][0]=res+1;
					id[z[i].id]=cnt;
				}else if(res+1>dp[z[i].id][1]){
					dp[z[i].id][1]=res+1;
				}
			}
			up(1,z[i].id);
		}
		dfs3(1,0);
		for(int i=1;i<=n;i++)printf("%d\n",max(ans[i],dp[i][0]));
		vv.clear();
		for(int i=1;i<=n;i++)v[i].clear();
	}
	return 0;
}

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169