Codeforces 490F Treeland Tour 樹上的最長上升子序列

Codeforces 490F Treeland Tour 樹上的最長上升子序列

題目鏈接：點擊打開鏈接

題意：

給定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[] 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;
}