CF490F Treeland Tour

题意：给定一棵带点权树，求树上最长上升子序列的长度$(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; } ```