Sol

怎么没人写长剖。

考虑在 LCA 处合并链，那么我们应当对每个节点存储子树内到其的 LIS 和 LDS 信息。通常来说我们考虑对每个终末值存储其子序列长度，这样借助点分治或者 DSU on Tree 之类的可以做到

O(n\log^2n)

。

考虑换维，对每个长度存储其可能的最小、最大终末值，这样一个点有用的状态只有其子树深度个，并且具有单调性。考虑长剖，在链头处维护信息，每个点初始状态直接继承长儿子，然后尝试使用当前点更新，接着平凡地枚举轻儿子更新答案、更新链信息即可。注意使用轻儿子更新链信息时应将当前点加入轻链。

考虑如何将链头尝试加入链信息，以 LIS 为例，也就是对每个最小值不超过链头值的长度，尝试更新其后一位的信息为当前链头值。由于整个序列具有单调性，因此我们只需要也只能修改首个超过链头值的位置，二分即可。

复杂度是

O(n\log n)

，跑得挺快。

Code

CPP

int n;
int a[N];
vec<int> g[N];

int dep[N],son[N],top[N];
void dfs0(int x,int f){
	for(auto y:g[x])if(y!=f){
		dfs0(y,x);
		if(dep[y]>dep[son[x]])son[x]=y;
	}
	dep[x]=dep[son[x]]+1;
}
void dfs1(int x,int f,int tp){
	top[x]=tp;
	if(son[x])dfs1(son[x],x,tp);
	for(auto y:g[x])if(y!=f&&y!=son[x])dfs1(y,x,y);
}
int ans,p;
vec<int> f[N],h[N];
#define Find(f,v) (int)(lower_bound(f.begin(),f.end(),v)-f.begin())
void dfs(int x,int fa){
	if(son[x])dfs(son[x],x);
	p=Find(f[top[x]],a[x]),chmin(f[top[x]][p],a[x]);
	p=Find(h[top[x]],-a[x]),chmin(h[top[x]][p],-a[x]);
	for(auto y:g[x])if(y!=fa&&y!=son[x]){
		dfs(y,x);
		rep(i,1,dep[y]){
			if(f[y][i]<inf)chmax(ans,i+Find(h[top[x]],-f[y][i])-1);
			if(h[y][i]<0)chmax(ans,i+Find(f[top[x]],-h[y][i])-1);
		}
		p=Find(f[y],a[x]),chmin(f[y][p],a[x]);
		p=Find(h[y],-a[x]),chmin(h[y][p],-a[x]);
		rep(i,1,dep[y]+1)chmin(f[top[x]][i],f[y][i]),chmin(h[top[x]][i],h[y][i]);
	}
}

inline void Main(){
	cin>>n;
	rep(i,1,n)cin>>a[i];
	rep(i,2,n){
		int a,b;cin>>a>>b;
		g[a].pub(b);g[b].pub(a);
	}
	dfs0(1,0),dfs1(1,0,1);
	rep(i,1,n)if(i==top[i])f[i].assign(dep[i]+2,inf),h[i].assign(dep[i]+2,0),f[i][0]=0,h[i][0]=-inf;
	dfs(1,0);
	chmax(ans,Find(f[1],inf)-1),chmax(ans,Find(h[1],0)-1);
	put(ans);
}

题解：P10241 [THUSC 2021] 白兰地厅的西瓜

文章操作

Sol

Code

相关推荐

评论

题解：P10241 [THUSC 2021] 白兰地厅的西瓜