1.dfs

java 代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
    //记录根节点-->>子节点
    static HashMap<Integer,List<Integer>> map = new HashMap<>();
    static int res = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for (int i = 2; i <= m+n; i++) {
            //父节点-->>子节点
            add(scanner.nextInt(),i);
        }
        //最长距离实际上就是该树中某节点到最远和次远的根节点距离之和的最大值
        dfs(1);
        System.out.println(res);
    }

    //向上返回以root为根的最大深度
    private static int dfs(int root) {
        List<Integer> list = map.get(root);
        if (list == null){
            return 1;
        }
        int max1 = 0;
        int max2 = 0;
        for (Integer child : list) {
            int h = dfs(child);
            if (h > max1){
                max2 = max1;
                max1 = h;
            }else if (h > max2){
                max2 = h;
            }
        }
        res = Math.max(res,max1+max2);
        return max1+1;
    }

    private static void add(int p, int c) {
        List<Integer> list = map.get(p);
        if (list == null){
            list = new ArrayList<>();
            map.put(p,list);
        }
        list.add(c);
    }
}

2.题目提供的条件却没有满足，如果满足了交换机父节点的标号比自己的小，直接一维数组一次遍历即可得出答案。

该解法提交不通过，因为题目给出的条件，输入用例没有满足

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int total = m + n;
//        boolean[] flag = new boolean[total+1];
        int[] p = new int[total+1];
        int[] h = new int[total+1];
        p[1] = 1;//根节点的父节点是自己
        for (int i = 0; i < total+1; i++) {
            h[i] = 1;//初始化所有的高度为1
        }
        for(int i = 2 ; i < total+1 ;i++){
            p[i] = input.nextInt();
        }
        int res = 0;
        for (int i = m+n; i > 1 ; i--) {
            int ch = h[i];//当前节点的高度
            int ph = h[p[i]];//父节点的高度
            res = Math.max(res,ch + ph - 1);
            h[p[i]] = Math.max(ph,ch+1);
        }
        System.out.println(res);
    }
}