景区导游

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

public class Main {
    static final int N = 100010, M = (int) (Math.log(N) / Math.log(2) + 2);
    static int[][] f = new int[N][M];
    static int[] deep = new int[N], path = new int[N];
    static long[] dis = new long[N];//记录dis[i]距离祖节点0的距离
    static ArrayList<ArrayList<Pair>> head = new ArrayList<>();
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            head.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }

        dfs(1, 0);
        long sum = 0;
        for (int i = 1; i <= m; i++) {
            path[i] = sc.nextInt();
            sum += getDis(path[i], path[i - 1]);
        }

        for (int i = 1; i <= m; i++) {
            long d1 = getDis(path[i - 1], path[i]);//计算i到i - 1的距离
            long d2 = getDis(path[i], path[i + 1]);//计算i到i+1的距离
            long d3 = getDis(path[i - 1], path[i + 1]);//计算i - 1到i + 1的距离
            long ans = sum - d1 - d2 + d3;
            System.out.print(ans + " ");
        }
    }

    static int lca(int a, int b) {
        if (deep[a] < deep[b]) {
            int temp = a;
            a = b;
            b = temp;
        }

        for (int i = M - 1; i >= 0; i--) {
            if (deep[f[a][i]] >= deep[b])
                a = f[a][i];
        }

        if (a == b) return a;
        for (int i = M - 1; i >= 0; i--) {
            if (f[a][i] != f[b][i]) {
                a = f[a][i];
                b = f[b][i];
            }
        }

        return f[a][0];
    }

    static long getDis(int a, int b) {
        if (a == 0 || b == 0) return 0;
        return dis[a] + dis[b] - 2 * dis[lca(a, b)];
    }

    static void dfs(int u, int p) {
        deep[u] = deep[p] + 1;
        f[u][0] = p;
        for (int i = 1; i < M; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }

        for (Pair item : head.get(u)) {
            int v = item.x;
            int w = item.y;
            if (v == p) continue;
            dis[v] = dis[u] + w;//记录距离
            dfs(v, u);
        }
    }

    static void add(int a, int b, int c) {
        head.get(a).add(new Pair(b, c));
    }
}

class Pair {
    int x;
    int y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}