solution.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

//动态链表ArrayList
class Vertex {
    ArrayList<Integer> V = new ArrayList();
}

class Edge {
    ArrayList<Integer> E = new ArrayList();
}

public class Main {

    final static int INF = 0X3f3f3f3f;
    final static int maxn = 100000;// 开100000数组才过，我r
    static Vertex v[] = new Vertex[maxn + 5];// v[i]存储与i相邻接的节点
    static Edge e[] = new Edge[maxn + 5];// e[i]存储与i相邻接的边，与v[i]一一对应
    static boolean vis[] = new boolean[maxn + 5];// 防止重复访问
    static int dis[] = new int[maxn + 5];// 存储原始节点到各节点的dfs距离

    static void init(int n)// 初始化
    {
        for (int i = 0; i < n; i++) {
            v[i] = new Vertex();
            e[i] = new Edge();
        }
    }

    static void dfs(int a) {
        int len = v[a].V.size();
        vis[a] = true;
        for (int i = 0; i < len; i++)// 遍历邻接节点
        {
            int j = v[a].V.get(i);
            if (!vis[j] && e[a].E.get(i) != INF) {

                vis[j] = true;
                dis[j] = dis[a] + e[a].E.get(i);
                // System.out.println(a+" "+j+" "+dis[j]);
                dfs(j);
                vis[j] = false;// 回溯
            }
        }
    }

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();

        init(n);
        for (int i = 0; i < n - 1; i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            int d = cin.nextInt();
            v[a - 1].V.add(b - 1);// 节点从零开始
            e[a - 1].E.add(d);
            v[b - 1].V.add(a - 1);
            e[b - 1].E.add(d);
        }
        Arrays.fill(vis, false);
        Arrays.fill(dis, INF);
        dis[0] = 0;
        dfs(0);// 第一次遍历
        long max = -1;
        int temp = -1;
        for (int i = 0; i < n; i++) {
            if (dis[i] > max) {
                max = dis[i];
                temp = i;
            }
        }
        // System.out.println(temp);

        Arrays.fill(vis, false);
        Arrays.fill(dis, INF);
        dis[temp] = 0;
        dfs(temp);// 第二次遍历
        long ans = -1;// 防止越界
        for (int i = 0; i < n; i++) {
            if (dis[i] > ans) {
                ans = dis[i];
                temp = i;
            }
        }
        // System.out.println(ans);
        ans = ans * 10 + ans * (ans + 1) / 2;// 如果ans是int的话，有可能越界
        System.out.println(ans);
        cin.close();
    }

}