毛草球:第三题ac代码(树上的最长路径)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author zhaole.myy
* @date 2019/9/24
*/
public class bd2019092403 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
List<List<Integer>> l = new ArrayList<>();//向下可达
for (int i = 0; i < n; i++) {
l.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
int father = sc.nextInt();
int son = sc.nextInt();
if (a[father - 1] < a[son - 1]) l.get(father - 1).add(son - 1);
else if (a[father - 1] > a[son - 1]) l.get(son - 1).add(father - 1);
}
sc.close();
System.out.println(answer(a,l));
}
private static int answer(int[] a, List<List<Integer>> l) {
int[] longest=new int[a.length];
for (int i = 0; i <longest.length ; i++) {
longest[i]=getLongest(i,l);
}
int max=Integer.MIN_VALUE;
for (int i = 0; i <longest.length ; i++) {
if(max<longest[i]) max=longest[i];
}
return max;
}
private static int getLongest(int i,List<List<Integer>> l){
if(l.get(i).size()==0) return 1;
List<Integer> canArrive=l.get(i);
int max=getLongest(canArrive.get(0),l);
for (int j = 1; j < canArrive.size(); j++) {
int t=getLongest(canArrive.get(j),l);
if(max<t) max=t;
}
return max+1;
}
}