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

· · 题解

Sol

怎么没人写长剖。

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

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

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

复杂度是 O(n\log n)，跑得挺快。

Code

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);
}