【链剖】求树上最长不降序列
文章目录
Petrozavodsk Summer-2017. JOI TST 2012 Selection.
输入n(<=1e5)
再输入n个ai,每个点的权值。
再输n-1条树边。
求树的路径上的最长不降子序列。
求一维的不降子序列常见思路是维护一个权值树状数组。
容易考虑到树有分叉,所用权值数据结构要启发式合并。
然而即使合并了由于路径(u,v)的lca不一定是中子序列的点,也无法有效查询(u,v)的最长子序列。
考虑轻重链剖分。
做到节点u,DFS递归完成节点u的轻儿子,对于每个轻儿子,都会带上来个树状数组,我们暂时不要它,即抹除该树状数组。
再DFS递归完成u的重儿子,不抹除其树状数组。
再枚举u的每个轻儿子,对于每个轻儿子,将其整颗子树拉出来,每个点依次考虑成序列中的点来计算序列长度(不会超时,因为每个点最多被拉出来logn次,链剖的性质保证了每个节点到根的路径只有logn个轻边,logn条重链),由于在DFS时可以算出自底向上最长链是F[po],于是可以直接把树状数组(已经并完的部分)的值和F[po]相加得到序列长度。做完这个轻儿子后,将整颗轻儿子子树并入树状数组。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std ;
const int N = 1e5 + 10 ;
int n , m ;
int h[N] ;
int tr[2][N] ;
int Ask( int x , int id ) {
int ret = 0 ;
for( ; x > 0 ; x-=x&-x ) ret = max( tr[id][x] , ret ) ;
return ret ;
}
void Erase( int id , int x ) {
for( ; x<=m ; x+=x&-x ) tr[id][x] = 0 ;
}
struct Edge {
int y , l ;
}f[N*2] ;
int g[N] , T ;
void Ins( int x , int y ) {
f[++T].y = y , f[T].l = g[x] , g[x] = T ;
f[++T].y = x , f[T].l = g[y] , g[y] = T ;
}
int fa[N] , si[N] , F[N][2] ;
void Calc( int po ) {
si[po] = 1 ;
for( int k = g[po] ; k ; k = f[k].l ) if ( fa[po] != f[k].y ) {
fa[ f[k].y ] = po ;
Calc( f[k].y ) ;
si[po] += si[ f[k].y ] ;
}
}
int di[N] , ans ;
int lis[N] , tot ;
void Brute_Tour( int po ) {//暴力遍历轻儿子子树,不会超时
lis[++tot] = po ;
for( int k=g[po] ; k ; k=f[k].l ) if( fa[po] != f[k].y ) {
Brute_Tour( f[k].y ) ;
}
}
void Modify( int x , int va , int id ) {
for( ; x<=m ; x+=x&-x ) tr[id][x] = max( tr[id][x] , va ) ;
}
void Dfs( int po ) {
vector< pair< int , int > > son ;
F[po][0] = F[po][1] = 1 ;
son.clear() ;
for( int k = g[po] ; k ; k=f[k].l ) if( fa[po] != f[k].y ) {
son.push_back( make_pair( si[ f[k].y ] , f[k].y ) ) ;
}
int cnt = son.size() ;
sort( son.begin() , son.end() ) ; //区分轻重儿子,最后一个是重儿子。
for( int i=0 ; i<cnt ; i++ ) {//递归求出F[po][0,1],即自底向上的最长序列长度
int nx = son[i].second ;
Dfs( nx ) ;
F[po][0] = max( F[po][0] , Ask( h[po]-1 , 0 ) +1 ) ;
F[po][1] = max( F[po][1] , Ask( m-h[po] , 1 ) +1 ) ;
if( i!=cnt-1 ) {
tot = 0 ;
Brute_Tour( nx ) ;
for( int j=1 ; j<=tot ; j++ ) {//抹除轻儿子树状数组
Erase( 0 , h[ lis[j] ] ) ;
Erase( 1 , m-h[ lis[j] ]+1 ) ;
}
}
}
ans = max( ans , max( F[po][0] , F[po][1] ) );
Modify( h[po] , F[po][0] , 0 ) ;
Modify( m-h[po]+1 , F[po][1] , 1 ) ;
for( int i=0 ; i<cnt-1 ; i++ ) {
int nx = son[i].second ;
tot = 0 ;
Brute_Tour( nx ) ;
for( int j=1 ; j<=tot ; j++ ) {
int ths = lis[j] ;
ans = max( ans , F[ths][0] + Ask( m-h[ths] , 1 ) ) ;//轻儿子子树点ths与重儿子以及已经遍历过的轻儿子合并的树状数组链接,认为ths到po之间没别的序列上的点
ans = max( ans , F[ths][1] + Ask( h[ths]-1 , 0 ) ) ;
}
for( int j=1 ; j<=tot ; j++ ) {
int ths = lis[j] ;
Modify( h[ths] , F[ths][0] , 0 ) ; //将刚刚的子树并入树状数组
Modify( m-h[ths]+1 , F[ths][1] , 1 ) ;
}
}
}
int main() {
//freopen("In","r",stdin ) ;
scanf("%d",&n ) ;
for( int i=1 ;i<=n ; i++ ) {
scanf("%d",&h[i] ) ;
di[i] = h[i] ;
}
sort( di+1 , di+1+n ) ;
m = unique( di+1 , di+1+n ) - ( di + 1 ) ;
for( int i=1 ; i<=n ; i++ ) h[i] = lower_bound( di+1 , di+1+m , h[i] ) - di ;
for( int i=1 ;i<n ; i++ ) {
int x , y ;
scanf("%d%d",&x,&y ) ;
Ins( x , y ) ;
}
Calc( 1 ) ;
ans = 0 ;
Dfs( 1 ) ;
printf("%d\n",ans ) ;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论