题解CF490F Treeland Tour

树上的最长上升子序列问题，先给出O(n^2logn)的算法。

虽然有更优的动态开点权值线段树的做法，但是我不太会写。以后慢慢补上吧。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define it register int
 4 #define il inline
 5 using namespace std;
 6 const int N=2000005;
 7 int n,a[N],h[N],nxt[N],adj[N],w[N],s[N],top,t,ans,fa[N]; 
 8 il int Max(it p,it q){
 9     return p>q?p:q;
10 }
11 il void add(it u,it v){
12     nxt[++t]=h[u],h[u]=t,adj[t]=v;
13     nxt[++t]=h[v],h[v]=t,adj[t]=u;
14 }
15 void fr(int &num){
16     num=0;char c=getchar();int p=1;
17     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
18     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
19     num*=p;
20 }
21 il void dfs(it x,it fa){
22     it now=lower_bound(s+1,s+1+n,w[x])-s; 
23     ans=Max(ans,now);it tx=s[now];s[now]=w[x];
24     for(it i=h[x];i;i=nxt[i])
25         if(adj[i]!=fa)
26             dfs(adj[i],x);
27     s[now]=tx;
28 }
29 int main(){
30     fr(n);
31     for(it i=1;i<=n;++i) fr(w[i]),s[i]=0x7fffffff;
32     for(it i=1,u,v;i<n;++i) fr(u),fr(v),add(u,v);
33     for(it i=1;i<=n;++i) dfs(i,-1);
34     printf("%d",ans); 
35     return 0;
36 }

View Code

我们每次遍历以当前节点为根的树的最长上升子序列。每次dfs之前求一下w[x]可以放的位置，dfs之后再还原原数。这样我们可以保证递归到叶子节点时我们求出了子树的最优解。