CF490F Treeland Tour

2018-10-08 15:52:04


题意:给定一棵带点权树,求树上最长上升子序列的长度 $(n<=6000)$


这个数据范围,可以很暴力

用朴素求解LIS的 $nlogn$ 做法,做 $n$ 次 $dfs$

$n^2logn$ 的复杂度可以跑过

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=6005;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,w[N],num,head[N],ans,f[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k,int fa)
{
    int pos=lower_bound(f+1,f+n+1,w[k])-f;
    ans=max(ans,pos); int tmp=f[pos]; f[pos]=w[k];
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v!=fa) dfs(v,k);
    }
    f[pos]=tmp;
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;w[i++]=read());
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    memset(f,127/3,sizeof(f));
    for (reg int i=1;i<=n;i++) dfs(i,0);
    printf("%d\n",ans);
    return 0;
}

要是数据范围再大一点这个就 $GG$ 了

$Q:$ 那咋办啊

$A:$ 对于每个点,维护以它子树内的点为结尾的 $LIS$ 和 $LDS$ ,放到权值线段树中合并信息

$Q:$ 咋更新答案啊

$A$ :用(左儿子的 $LIS+$ 右儿子的 $LDS$ )和(左儿子的 $LDS+$ 右儿子的 $LIS$ )更新

别忘了离散化一下

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=6005;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,w[N],num,head[N],t[N],tot,rt[N],cnt,ans,ret;
int ls[N*40],rs[N*40],lis[N*40],lds[N*40];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void insert(int &now,int l,int r,int x,int c,int *a)
{
    if (!now) now=++cnt; a[now]=max(a[now],c);
    if (l==r) return; int mid=(l+r)>>1;
    if (x<=mid) insert(ls[now],l,mid,x,c,a);
    else insert(rs[now],mid+1,r,x,c,a);
}
int merge(int a,int b)
{
    if (!a) return b; if (!b) return a;
    lis[a]=max(lis[a],lis[b]); lds[a]=max(lds[a],lds[b]);
    ans=max(ans,max(lis[ls[a]]+lds[rs[b]],lds[rs[a]]+lis[ls[b]]));
    ls[a]=merge(ls[a],ls[b]); rs[a]=merge(rs[a],rs[b]);
    return a;
}
int query(int L,int R,int l,int r,int now,int *a)
{
    if (l>R||r<L||!now) return 0;
    if (l>=L&&r<=R) return a[now];
    int mid=(l+r)>>1;
    if (mid>=R) return query(L,R,l,mid,ls[now],a);
    if (mid<L) return query(L,R,mid+1,r,rs[now],a);
    return max(query(L,mid,l,mid,ls[now],a),query(mid+1,R,mid+1,r,rs[now],a));
}
void dfs(int k,int fa)
{
    int mlis=0,mlds=0;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue; dfs(v,k);
        int ilis=query(1,w[k]-1,1,tot,rt[v],lis);
        int ilds=query(w[k]+1,tot,1,tot,rt[v],lds);
        rt[k]=merge(rt[k],rt[v]);
        ans=max(ans,max(ilis+mlds,ilds+mlis)+1);
        mlis=max(mlis,ilis); mlds=max(mlds,ilds);
    }
    insert(rt[k],1,tot,w[k],mlis+1,lis);
    insert(rt[k],1,tot,w[k],mlds+1,lds);
}
int main()
{
    n=read(); cnt=n;
    for (reg int i=1;i<=n;i++) w[i]=t[i]=read(),rt[i]=i;
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    sort(t+1,t+n+1);
    tot=unique(t+1,t+n+1)-t-1;
    for (reg int i=1;i<=n;i++) w[i]=lower_bound(t+1,t+tot+1,w[i])-t;
    dfs(1,0); printf("%d\n",ans);
    return 0;
}