题目链接：点击打开链接

题意：

给定n个点的树。

以下n个数表示点权。

以下n-1行给出树。

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

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

思路：

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

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

import java.io.PrintWriter;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class Main {

	int max(int x, int y) {

		return x > y ? x : y;

	}

	static int N = 6050;

	int[] a = new int[N], len = new int[N];

	int n;

	int ans;

	ArrayList<Integer>[] G = new ArrayList[N];

	int[] Stack = new int[N];

	int top;

	void find(int u, int fa) {

		int pos = -1, val = -1;

		if(a[u]>Stack[top-1]){

			pos = -2;//-2表示新加了一个元素

			Stack[top++] = a[u];

			ans = max(ans, top);

		}

		else

		{

			int l = 0, r = top-1, siz = 0;

			while(l <= r){

				int mid = (l+r)>>1;

				if(Stack[mid] < a[u])

					l = mid+1;

				else

				{

					r = mid-1;

					siz = mid;

				}

			}

			pos = siz; val = Stack[siz];

			Stack[pos] = a[u];

		}

		for(int i = 0; i < G[u].size(); i++){

			int v = G[u].get(i); if(v == fa)continue;

			find(v, u);

		}

		if(pos != -1){

			if(pos == -2)top--;

			else {

				Stack[pos] = val;

			}

		}

	}

	void solve(int u) {

		for(int i = 0; i < G[u].size(); i++){

			int v = G[u].get(i);

			top = 0;

			Stack[top++] = a[u];

			find(v, u);

		}

	}

	void input() {

		n = cin.nextInt();

		for (int i = 1; i <= n; i++) {

			G[i] = new ArrayList();

			a[i] = cin.nextInt();

		}

		for (int i = 1, u, v; i < n; i++) {

			u = cin.nextInt();

			v = cin.nextInt();

			G[u].add(v);

			G[v].add(u);

		}

	}

	public void work() {

		input();

		ans = 1;

		for (int i = 1; i <= n; i++)

			solve(i);

		out.println(ans);

	}

	Main() {

		cin = new Scanner(System.in);

		out = new PrintWriter(System.out);

	}

	public static void main(String[] args) {

		Main e = new Main();

		e.work();

		out.close();

	}

	public Scanner cin;

	public static PrintWriter out;

}