Nhận xét: Đồ thị đã cho là 1 cây

Với mỗi truy vấn ~x_i=0~, giả sử ~a_i~ là đỉnh xa gốc hơn (con của ~b_i~), nhận thấy để đạt được cách nối cặp sao cho tổng khoảng cách giữa các cặp là nhỏ nhất, ta sẽ luôn ưu tiên nối các hạt giống trong cây con của đỉnh ~a_i~ với các chậu cây cũng trong cây con của đỉnh ~a_i~. Do đó, số cặp đi qua cạnh nối giữa ~a_i~ và ~b_i~ chỉ đơn giản là chênh lệch giữa số hạt giống và số chậu cây trong cây con của ~a_i~. Coi mỗi phép đặt hạt giống là ~+x_i~ và đặt chậu cây là ~-x_i~, đáp án cho mỗi câu hỏi là trị tuyệt đối của tổng giá trị của các đỉnh trong cây con của ~a_i~.

Sử dụng kĩ thuật trải cây (Euler Tour Technique) để giải. Sau khi chuyển cây đã cho thành một mảng, bài toán đã trở nên dễ dàng hơn nhiều.

Giờ ta chỉ cần sử dụng một cấu trúc dữ liệu như cây IT hay cây BIT để cập nhật giá trị một điểm và tính tổng một khoảng trong ~\mathcal{O}(\log{n})~.

Tổng độ phức tạp: ~\mathcal{O}(n + q\log{n})~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, q;
int timer, tin[N], tout[N];
long long bit[N];
vector<int> adj[N];

long long getSum(int p) {
    int idx = p;
    long long ans = 0;
    while (idx > 0) {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}

long long getSum(int l, int r) {
    return getSum(r) - getSum(l - 1);
}

void update(int u, int v) {
    int idx = u;
    while (idx <= n) {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

void dfs(int u, int p = 0) {
    tin[u] = ++timer;
    for (int v : adj[u]) 
        if (v != p) 
            dfs(v, u);
    tout[u] = timer;
}

bool is_ancestor(int u, int v) { // kiểm tra xem u có phải tổ tiên của v hay không
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void solve() {
    timer = 0;
    cin >> n >> q; 
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    while (q--) {
        int a, b, x; cin >> a >> b >> x;
        if (x == 0) {
            if (is_ancestor(a, b)) swap(a, b);
            cout << abs(getSum(tin[a], tout[a])) << "\n";
        } else {
            update(tin[a], x);
            update(tin[b], -x);
        }
    }

    // reset lại cho test tiếp theo
    fill_n(bit, n + 1, 0);
    for (int i = 1; i <= n; i++) 
        adj[i].clear();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int c; cin >> c;
    while (c--) 
        solve();
    return 0;
}