第十四届蓝桥杯省赛 C++B组 ---- 景区导游

第十四届蓝桥杯省赛 C++B组 ---- 景区导游

LCA

原题连接

​ lca 同时得到按原来路径走的总时间

​ 最后输出时处理跳过某个点的时间

​ 预处理用 bfs 或 dfs 都可以

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * ClassName:Main
 * Package:lqb
 * Description:
 *
 * @author:LH寒酥
 * @create:2023/11/17-16:54
 * @version:v1.0
 */
public class Main {
    static final int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
    static int n, idx;
    static int[] h = new int[N], ne = new int[M], e = new int[M], w = new int[M];
    static int[][] fa = new int[N][18];
    static long[][] faDis = new long[N][18];
    static int[] depth = new int[N], a = new int[N];

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

    static void bfs(int root) {
        Arrays.fill(depth, INF);
        depth[0] = 0;
        depth[root] = 1;
        fa[root][0] = 0;
        faDis[root][0] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int t = queue.poll();
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i]; int c = w[i];
                if (depth[j] > depth[t] + 1) {
                    depth[j] = depth[t] + 1;
                    queue.add(j);
                    fa[j][0] = t;
                    faDis[j][0] = c;
                    for (int k = 1; k <= 17; k ++) {
                        faDis[j][k] = faDis[fa[j][k - 1]][k - 1] + faDis[j][k - 1];
                        fa[j][k] = fa[fa[j][k- 1]][k - 1];
                    }
                }
            }
        }
    }

    static void dfs(int x, int father, long dis, int hh) {
        depth[x] = hh;
        faDis[x][0] = dis;
        fa[x][0] = father;

        for (int i = 1; i <= 17; i ++) {
            faDis[x][i] = faDis[x][i - 1] + faDis[fa[x][i - 1]][i - 1]; 
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        }

        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == father) continue;
            dfs(j, x, w[i], hh + 1);
        }
    }

    static long lca(int a, int b) {
        long ans = 0;
        if (depth[a] < depth[b]) {
            int t = a;
            a = b;
            b = t;
        }
        for (int i = 17; i >= 0; i --) {
            if (depth[fa[a][i]] >= depth[b]) {
                ans += faDis[a][i]; // 先写
                a = fa[a][i];
            }
        }

        if (a == b) return ans;

        for (int i = 17; i >= 0; i --) {
            if (fa[a][i] != fa[b][i]) {
                ans += faDis[a][i] + faDis[b][i]; // 先写这个, 然后再更新
                a = fa[a][i];
                b = fa[b][i];
            }
        }
        ans += faDis[a][0] + faDis[b][0];
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);

        Arrays.fill(h, -1);

        for (int i = 0; i < n - 1; i ++) {
            s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int w = Integer.parseInt(s[2]);
            add(a, b, w); add(b, a, w);
        }

//        bfs(1);
        dfs(1, 0, 0, 1);

        long res = 0;
        s = br.readLine().split(" ");
        for (int i = 1; i <= k; i ++) {
            a[i] = Integer.parseInt(s[i - 1]);
            if (i > 1) res += lca(a[i], a[i - 1]);
//            System.out.println(a[i] + " " + res);
        }

        for (int i = 1; i <= k; i ++) {
            if (i == 1) System.out.print(res - lca(a[1], a[2]) + " ");
            else if (i == k) System.out.print(res - lca(a[k], a[k - 1]) + " ");
            else System.out.print(res - lca(a[i], a[i - 1]) - lca(a[i], a[i + 1]) + lca(a[i - 1], a[i + 1]) + " ");
        }
    }
}

刚学LCA, 先留在这