题解 | #树上上升序列#
树上上升序列
http://www.nowcoder.com/questionTerminal/8eda05798f8c486a9f954432515ae436
#大佬解答下为何有部分算例不能通过
import java.util.LinkedList; import java.util.List; import java.util.Scanner;
import java.util.LinkedList; import java.util.List; import java.util.Scanner;
public class Main { static int res; static int n; static int[] weights; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); weights = new int[n+1]; List[] graph = new LinkedList[n+1]; for (int i = 1; i <= n; i++) { graph[i] =new LinkedList(); weights[i] = scanner.nextInt(); } for (int i = 0; i < n-1; i++) { graph[scanner.nextInt()].add(scanner.nextInt()); } for (int i = 1; i <=n; i++) { dfs(i,graph,1); } System.out.println(res); } public static void dfs(int s, List[]graph,int step){ res = Math.max(res,step); for(int p:graph[s]){ if(weights[p]>weights[s]){ int newstp = step+1; dfs(p,graph, step+1); } }
