多叉树的直径

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution {
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */

    static int[] h;
    static int[] e;
    static int[] w;
    static int[] ne;
    static int idx = 0;
    static int[] d;//以N为根节点的子树的深度；
    static int ans = 0;
    static boolean[] st;  //无向图防止子节点回到父节点
    static int cao;

    static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        // write code here
        int N = n;
        int M = N*3;
        e = new int[M];
        h = new int[N];
        w = new int[M];
        ne = new int[M];
        d = new int[N];
        st = new boolean[N];
        Arrays.fill(h, -1);
        for (int i = 0; i < n-1; i++){
            add(Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]);
            add(Tree_edge[i].end, Tree_edge[i].start, Edge_value[i]);
        }

        dfs(1);
        Arrays.fill(d, 0);
        Arrays.fill(st, false);
        dfs(ans);
        return d[ans];
    }

    void dfs(int u) {
        if (st[u]) return;
        st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) { // 是否被遍历过
                d[j]=d[u]+w[i];
                if(d[j]>d[ans])ans=j;
                dfs(j);
            }
        }
    }

}

//可参考https://www.bilibili.com/video/BV1qA411t7LR?from=search&seid=13550771883067952709，比较类似
import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> nei = new ArrayList<>();//邻接列表——>存储无向图的关系
    HashMap<ArrayList<Integer>, Integer> edge = new HashMap<>();//哈希表：存储边的权重
    int ans=Integer.MIN_VALUE;//最终结果
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        
        //初始化邻接表
        for(int i=0;i<n;i++){
            nei.add(new ArrayList<>());
        }
        //邻接表和哈希表的写入
        for(int i=0;i<Tree_edge.length;i++){
            //无向表，所以两次写入
            int a=Tree_edge[i].start;
            int b=Tree_edge[i].end;
            //邻接列表
            nei.get(a).add(b);
            nei.get(b).add(a);
            //哈希表
            ArrayList<Integer> tmp=new ArrayList<>();
            tmp.add(a);
            tmp.add(b);
            edge.put(tmp,Edge_value[i]);
            tmp=new ArrayList<>();
            tmp.add(b);
            tmp.add(a);
            edge.put(tmp,Edge_value[i]);
        }
        boolean[] v=new boolean[n];
        dfs(0,v);
        return ans;
 }
    private int dfs(int root,boolean[] v){
        //初始化及出口条件
        v[root]=true;
        ArrayList<Integer> ls=new ArrayList<>();
        ls=nei.get(root);
        int m1=Integer.MIN_VALUE,m2=Integer.MIN_VALUE;//m1距离该节点最长的值，m2代表第2长的值
        //int m1=0,m2=0;
        //出口条件
        for(int k:ls){
            if(!v[k]){//标记为已经访问过的，则不访问
                ArrayList<Integer> e=new ArrayList<>();
                e.add(root);
                e.add(k);
                int res=Integer.MIN_VALUE;
                //递归，res代表该节点到本次的探索的长度
                res=dfs(k,v)+edge.get(e);
                //保证m1最长，m2第2长
                if(res>m1){
                    m2=m1;
                    m1=res;
                }
                else if(res>m2)
                    m2=res;
            }
        }
        //判断条件
        if(m1==Integer.MIN_VALUE){
            ans = Math.max(ans, 0);
        }
        else{
            if(m2==Integer.MIN_VALUE)
                ans = Math.max(ans, m1);
            else
                ans=Math.max(ans,m1+m2);
        }
        //从本节点出发，一直搜索到最后。将该节点设为未访问，便于从其它节点访问本节点
        v[root]=false;
        return Math.max(m1,0);//如果m1为末端或者为负，就要舍弃掉从root出发的所有路径，返回0
    }