给定n个点的树。

下面n个数表示点权。

下面n-1行给出树。

找一条链，然后找出这条链中的点权组成的最长上升子序列。

求：最长上升子序列的长度。

思路：

首先是维护一条链然后求答案，但是如果直接树形dp（记录每个点u，u往下递增和u往下递减的长度）会使序列是来回的，即递增和递减都在同一条链上。

枚举每个点作为子序列的开头，然后维护一条链进行LIS的nlogn做法。

[java] view plaincopy

1. import java.io.PrintWriter;  
2. import java.util.ArrayList;  
3. import java.util.Arrays;  
4. import java.util.Collections;  
5. import java.util.HashMap;  
6. import java.util.HashSet;  
7. import java.util.Iterator;  
8. import java.util.List;  
9. import java.util.Map;  
10. import java.util.Scanner;  
11. import java.util.Set;  
12. import java.util.TreeSet;  
13.   
14. public class Main {  
15.     int max(int x, int y) {  
16.         return x > y ? x : y;  
17.     }  
18.     static int N = 6050;  
19.     int[] a = new int[N], len = new int[N];  
20.     int n;  
21.     int ans;  
22.     ArrayList<Integer>[] G = new ArrayList[N];  
23.     int[] Stack = new int[N];  
24.     int top;  
25.     void find(int u, int fa) {  
26.         int pos = -1, val = -1;  
27.         if(a[u]>Stack[top-1]){  
28.             pos = -2;//-2表示新加了一个元素  
29.             Stack[top++] = a[u];  
30.             ans = max(ans, top);  
31.         }  
32.         else  
33.         {  
34.             int l = 0, r = top-1, siz = 0;  
35.             while(l <= r){  
36.                 int mid = (l+r)>>1;  
37.                 if(Stack[mid] < a[u])  
38.                     l = mid+1;  
39.                 else   
40.                 {  
41.                     r = mid-1;  
42.                     siz = mid;  
43.                 }  
44.             }  
45.             pos = siz; val = Stack[siz];  
46.             Stack[pos] = a[u];  
47.         }  
48.         for(int i = 0; i < G[u].size(); i++){  
49.             int v = G[u].get(i); if(v == fa)continue;  
50.             find(v, u);  
51.         }  
52.         if(pos != -1){  
53.             if(pos == -2)top--;  
54.             else {  
55.                 Stack[pos] = val;  
56.             }     
57.         }  
58.     }  
59.     void solve(int u) {  
60.         for(int i = 0; i < G[u].size(); i++){  
61.             int v = G[u].get(i);  
62.             top = 0;  
63.             Stack[top++] = a[u];  
64.             find(v, u);  
65.         }  
66.     }  
67.   
68.     void input() {  
69.         n = cin.nextInt();  
70.         for (int i = 1; i <= n; i++) {  
71.             G[i] = new ArrayList();  
72.             a[i] = cin.nextInt();  
73.         }  
74.         for (int i = 1, u, v; i < n; i++) {  
75.             u = cin.nextInt();  
76.             v = cin.nextInt();  
77.             G[u].add(v);  
78.             G[v].add(u);  
79.         }  
80.     }  
81.   
82.       
83.   
84.     public void work() {  
85.         input();  
86.         ans = 1;  
87.         for (int i = 1; i <= n; i++)  
88.             solve(i);  
89.         out.println(ans);  
90.     }  
91.   
92.     Main() {  
93.         cin = new Scanner(System.in);  
94.         out = new PrintWriter(System.out);  
95.     }  
96.   
97.     public static void main(String[] args) {  
98.         Main e = new Main();  
99.         e.work();  
100.         out.close();  
101.     }  
102.   
103.     public Scanner cin;  
104.     public static PrintWriter out;  
105. } 

Codeforces 490F Treeland Tour 树上的最长上升子序列