Bài toán yêu cầu tính tổng thời gian di chuyển trên một cây có trọng số trên các cạnh, với một lộ trình gồm k điểm. Cụ thể, chúng ta cần tính tổng thời gian sau mỗi lần di chuyển từ điểm thứ i đến điểm thứ i+1 trong lộ trình.

Phân tích bài toán

Cây được cho có trọng số trên các cạnh, biểu thị thời gian di chuyển giữa hai đỉnh liền kề. Lộ trình bao gồm k điểm, nghĩa là sẽ có k-1 lượt di chuyển.

Để tính thời gian di chuyển giữa hai điểm bất kỳ trong cây, chúng ta có thể sử dụng kỹ thuật tiền tố tổng (prefix sum) kết hợp với tìm tổ tiên chung gần nhất (Lowest Common Ancestor - LCA). Giả sử time[u] là tổng thời gian từ gốc đến đỉnh u. Thời gian di chuyển từ đỉnh u đến đỉnh v sẽ được tính bằng công thức:

time[u] + time[v] - 2 * time[LCA(u, v)]

Trong đó, LCA(u, v) là đỉnh tổ tiên chung gần nhất của u và v.

Bài toán yêu cầu tính tổng thời gian di chuyển sau mỗi bước. Nếu lộ trình là p1, p2, ..., pk, thì ở bước thứ i (với 1 <= i < k), chúng ta di chuyển từ pi đến p(i+1). Tuy nhiên, đề bài yêu cầu tính tổng thời gian sau k lần đi, tức là sau khi đi qua k điểm. Điều này có nghĩa là chúng ta cần tính tổng thời gian di chuyển từ p1 đến p2, rồi từ p2 đến p3, ..., và cuối cùng là từ p(k-1) đến pk. Tổng thời gian của toàn bộ lộ trình là tổng của tất cả các khoảng thời gian này.

Sau khi tính tổng thời gian cho toàn bộ lộ trình, chúng ta cần tính thời gian sau i lần di chuyển (tức là sau khi đến điểm thứ i+1 trong lộ trình). Nếu lộ trình ban đầu là p1, p2, ..., pk, thì chúng ta có thể hình dung một lộ trình "đầy đủ" mà không bỏ qua điểm nào. Sau đó, chúng ta sẽ xem xét việc bỏ qua các điểm. Việc bỏ qua điểm p(j+1) trong lộ trình pj -> p(j+1) -> p(j+2) sẽ thay thế hai lượt di chuyển pj -> p(j+1) và p(j+1) -> p(j+2) bằng một lượt di chuyển pj -> p(j+2).

Để giải quyết bài toán này, chúng ta sẽ:

1. Xây dựng cây và tính toán tiền tố thời gian từ gốc đến mỗi đỉnh.
2. Sử dụng thuật toán tăng sức mạnh (binary lifting) để xây dựng bảng lưu trữ tổ tiên và tính toán LCA hiệu quả.
3. Tính tổng thời gian di chuyển cho toàn bộ lộ trình ban đầu (không bỏ qua điểm nào).
4. Tính toán thời gian cho từng cặp di chuyển liền kề (ví dụ: từ pi đến p(i+1)) và từng cặp di chuyển có bỏ qua một điểm (ví dụ: từ pi đến p(i+2)).
5. Cuối cùng, tính tổng thời gian sau mỗi lần di chuyển bằng cách lấy tổng thời gian ban đầu, trừ đi thời gian của các lượt di chuyển bị bỏ qua và cộng thêm thời gian của lượt di chuyển thay thế.

Thuật toán tìm LCA bằng Binary Lifting

Tìm tổ tiên chung gần nhất (LCA) bằng phương pháp binary lifting bao gồm 3 bước chính:

1. Đưa về cùng độ sâu: Đảm bảo hai đỉnh cần tìm LCA có cùng độ sâu. Nếu một đỉnh có độ sâu lớn hơn, ta sẽ di chuyển nó lên cho đến khi bằng độ sâu của đỉnh kia.
2. Cùng nhau tìm tổ tiên: Sau khi đã ở cùng độ sâu, cả hai đỉnh cùng nhau di chuyển lên theo từng bước lũy thừa của 2 cho đến khi cha của chúng khác nhau. Điều này giúp đưa chúng đến gần tổ tiên chung nhất có thể mà vẫn còn khác nhau.
3. Xác định LCA: Đỉnh cha trực tiếp của một trong hai đỉnh sau bước 2 chính là LCA cần tìm.

Mã giả cho thuật toán LCA:

int LCA(int u, int v) {
    // Bước 1: Đưa về cùng độ sâu
    if (depth[v] > depth[u]) std::swap(u, v); // Đảm bảo u có độ sâu lớn hơn hoặc bằng v
    int diff_depth = depth[u] - depth[v];
    for (int i = LOGN; i >= 0; --i) { // LOGN là giá trị log2(MAXN)
        if ((diff_depth >> i) & 1) {
            u = parent[u][i]; // Di chuyển u lên bằng binary lifting
        }
    }

    if (u == v) return u; // Nếu sau khi đưa về cùng độ sâu mà u bằng v, thì v là tổ tiên của u

    // Bước 2: Cùng nhau tìm tổ tiên
    for (int i = LOGN; i >= 0; --i) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }

    // Bước 3: Xác định LCA
    return parent[u][0]; // Cha trực tiếp của u (hoặc v) là LCA
}

Mã nguồn tham khảo

Dưới đây là đoạn mã C++ minh họa cách triển khai bài toán:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

const int MAXN = 100010;
const int LOGN = 20; // log2(MAXN)

struct NodeInfo {
    int time_sum; // Tổng thời gian từ gốc
    int depth;    // Độ sâu của nút
};

NodeInfo node_data[MAXN];
int adjacency_list[MAXN]; // Sử dụng mảng để lưu trữ cạnh (ví dụ: index của cạnh trong mảng edge_data)
int edge_to[2 * MAXN];
int edge_weight[2 * MAXN];
int edge_next[2 * MAXN];
int edge_count = 1; // Bắt đầu từ 1 để dễ xử lý

int tour_points[MAXN]; // Lưu trữ các điểm trong lộ trình
int ancestors[MAXN][LOGN + 1]; // ancestors[u][i] là tổ tiên thứ 2^i của u

// Lưu trữ thời gian cho các cặp di chuyển:
// move_time[i][0]: thời gian từ tour_points[i] đến tour_points[i+1]
// move_time[i][1]: thời gian từ tour_points[i] đến tour_points[i+2] (bỏ qua tour_points[i+1])
long long move_time[MAXN][2];

int num_nodes, num_stops;

// Hàm thêm cạnh vào danh sách kề
void add_edge(int u, int v, int w) {
    edge_to[edge_count] = v;
    edge_weight[edge_count] = w;
    edge_next[edge_count] = adjacency_list[u];
    adjacency_list[u] = edge_count++;

    edge_to[edge_count] = u;
    edge_weight[edge_count] = w;
    edge_next[edge_count] = adjacency_list[v];
    adjacency_list[v] = edge_count++;
}

// Khởi tạo bảng tổ tiên cho binary lifting
void precompute_lca() {
    for (int j = 1; j <= LOGN; ++j) {
        for (int i = 1; i <= num_nodes; ++i) {
            ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
        }
    }
}

// Duyệt cây để tính độ sâu và tổng thời gian từ gốc
void dfs_init(int u, int parent, int current_depth = 1) {
    node_data[u].depth = current_depth;
    for (int i = adjacency_list[u]; i; i = edge_next[i]) {
        int v = edge_to[i];
        int weight = edge_weight[i];
        if (v == parent) continue;
        node_data[v].time_sum = node_data[u].time_sum + weight;
        ancestors[v][0] = u; // Lưu tổ tiên trực tiếp
        dfs_init(v, u, current_depth + 1);
    }
}

// Hàm tính LCA
int find_lca(int u, int v) {
    if (node_data[v].depth > node_data[u].depth) std::swap(u, v);
    int depth_diff = node_data[u].depth - node_data[v].depth;

    // Đưa u về cùng độ sâu với v
    for (int i = LOGN; i >= 0; --i) {
        if ((depth_diff >> i) & 1) {
            u = ancestors[u][i];
        }
    }

    if (u == v) return u;

    // Tìm LCA
    for (int i = LOGN; i >= 0; --i) {
        if (ancestors[u][i] != ancestors[v][i]) {
            u = ancestors[u][i];
            v = ancestors[v][i];
        }
    }
    return ancestors[u][0];
}

// Hàm tính tổng thời gian của toàn bộ lộ trình
long long calculate_total_time() {
    long long total_time = 0;
    for (int i = 1; i < num_stops; ++i) {
        int u = tour_points[i];
        int v = tour_points[i + 1];
        int lca = find_lca(u, v);
        long long current_leg_time = (long long)node_data[u].time_sum - node_data[lca].time_sum +
                                     (long long)node_data[v].time_sum - node_data[lca].time_sum;
        move_time[i][0] = current_leg_time; // Lưu thời gian di chuyển thông thường
        total_time += current_leg_time;
    }
    return total_time;
}

// Hàm tính thời gian cho các lượt di chuyển có bỏ qua điểm
void calculate_skipped_time() {
    for (int i = 1; i <= num_stops - 2; ++i) {
        int u = tour_points[i];
        int v = tour_points[i + 2];
        int lca = find_lca(u, v);
        move_time[i][1] = (long long)node_data[u].time_sum - node_data[lca].time_sum +
                          (long long)node_data[v].time_sum - node_data[lca].time_sum;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodes >> num_stops;
    for (int i = 1; i < num_nodes; ++i) {
        int u, v, t;
        std::cin >> u >> v >> t;
        add_edge(u, v, t);
    }

    dfs_init(1, 0); // Bắt đầu DFS từ nút 1
    precompute_lca();

    for (int i = 1; i <= num_stops; ++i) {
        std::cin >> tour_points[i];
    }

    long long total_route_time = calculate_total_time();
    calculate_skipped_time();

    for (int i = 1; i < num_stops; ++i) {
        // Thời gian sau lần di chuyển thứ i (đến điểm tour_points[i+1])
        // = Tổng thời gian lộ trình - thời gian lượt i (pi -> p(i+1)) - thời gian lượt i+1 (p(i+1) -> p(i+2))
        //   + thời gian lượt thay thế (pi -> p(i+2))
        long long time_after_move_i = total_route_time - move_time[i][0];
        if (i + 1 <= num_stops - 1) { // Đảm bảo có lượt đi tiếp theo
             time_after_move_i -= move_time[i+1][0];
        }
        if (i + 2 <= num_stops) { // Đảm bảo có lượt đi bỏ qua điểm
            time_after_move_i += move_time[i][1];
        }

        std::cout << time_after_move_i << (i == num_stops - 1 ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}