HLD: phân rã nặng nhẹ trên cây · Thuật toán Canuc80k

Cho một cây, mỗi đỉnh có một giá trị. Hỏi giá trị lớn nhất trên đường đi từ $u$ đến $v$ , và đôi khi đổi giá trị một đỉnh. Trên mảng, việc này là của cây phân đoạn. Trên cây thì không: đường đi không nằm liền nhau trong mảng nào cả.

Phân rã nặng nhẹ (HLD) chữa chỗ đó. Nó chia cây thành các chuỗi, đánh số sao cho mỗi chuỗi là một đoạn liên tiếp, và mọi đường đi chỉ cắt qua $O(\log n)$ chuỗi. Một thao tác trên đường thành $O(\log n)$ thao tác trên đoạn, tổng $O(\log^2 n)$ . Cách đánh số đúng còn giữ cả cây con thành một đoạn.

Chuỗi nặng

Với mỗi đỉnh, con nặng là con có cây con lớn nhất; cạnh tới nó là cạnh nặng, các cạnh còn lại là nhẹ. Đi theo một cạnh nhẹ từ $u$ xuống $c$ thì $sz(c) \le sz(u)/2$ , nên từ một đỉnh lên gốc chỉ qua tối đa $\log_2 n$ cạnh nhẹ. Các cạnh nặng nối thành chuỗi, mỗi chuỗi có một đỉnh đầu head.

Đánh số pos sao cho mỗi chuỗi là đoạn liên tiếp, từ đầu chuỗi xuống. Nếu đánh số theo DFS và đi con nặng trước, cây con của $v$ cũng là đoạn $[pos_v, pos_v + sz_v - 1]$ . Để khỏi đệ quy sâu tới $n$ tầng:

BFS từ gốc lấy par, dep; duyệt thứ tự BFS ngược để tính sz và heavy.
Một ngăn xếp chứa các đỉnh đầu chuỗi. Lấy đầu chuỗi $h$ , đi dọc chuỗi đánh số liên tiếp, gặp con nhẹ thì đẩy vào ngăn xếp. Con nhẹ của đỉnh thấp hơn được lấy ra trước, nên cây con nào cũng được đánh số liền một khối, đúng như DFS.

Trong hình, cạnh đậm là cạnh nặng, cạnh đứt là cạnh nhẹ. Đổi $u$ , $v$ để xem đường tách thành bao nhiêu đoạn liền trên mảng vị trí.

Đường

u \to v

tách thành các đoạn trên mảng.

Truy vấn đường. Khi $u, v$ khác chuỗi, đầu chuỗi nào sâu hơn thì chuỗi đó không chứa LCA: xử lý đoạn $[pos_{head}, pos]$ của nó rồi nhảy lên cha của đầu chuỗi. Khi cùng chuỗi, xử lý đoạn giữa hai đỉnh. Mỗi bên nhảy tối đa $\log n$ lần.

Hỏi nhanh

Cây là một đường thẳng $n$ đỉnh, gốc ở một đầu. Một truy vấn đường đi qua bao nhiêu chuỗi?

Ví dụGiá Trị Lớn Nhất Trên Đường

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh có giá trị. $q \le 2 \cdot 10^5$ thao tác: gán giá trị một đỉnh, hoặc hỏi giá trị lớn nhất trên đường $u \to v$ .

Lời giải. Chia cây thành các chuỗi nặng, đánh số đỉnh sao cho mỗi chuỗi là một đoạn liên tiếp, rồi đặt giá trị đỉnh vào cây phân đoạn cực đại theo số thứ tự đó. Gán một đỉnh là cập nhật điểm. Đường $u \to v$ cắt thành $O(\log n)$ đoạn chuỗi, mỗi đoạn hỏi cực đại một lần.

Bước 1: kích thước và con nặng. BFS từ gốc ghi par, dep và thứ tự order. Duyệt order từ cuối lên thì con luôn được xét trước cha, nên cộng được sz[u] vào cha, đồng thời chọn heavy[p] là con có cây con lớn nhất. Không dùng đệ quy nên cây dạng đường dài $2 \cdot 10^5$ không làm tràn ngăn xếp.

C++

vector<int> order = {root};
for (int i = 0; i < (int)order.size(); i++) {
    int u = order[i];
    for (int v : adj[u])
        if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, order.push_back(v);
}
for (int i = n - 1; i >= 0; i--) {
    int u = order[i], p = par[u];
    sz[u]++;
    if (p) {
        sz[p] += sz[u];
        if (!heavy[p] || sz[u] > sz[heavy[p]]) heavy[p] = u;
    }
}

Bước 2: đánh số theo chuỗi. Ngăn xếp st chứa các đỉnh đầu chuỗi. Lấy một đầu chuỗi h, đi theo heavy tới hết chuỗi và đánh số liên tiếp, nên cả chuỗi là một đoạn. Con nhẹ của mỗi đỉnh trên chuỗi là đầu một chuỗi mới, đẩy vào st.

C++

vector<int> st = {root};
while (!st.empty()) {
    int h = st.back();
    st.pop_back();
    for (int v = h; v; v = heavy[v]) {
        head[v] = h, pos[v] = cnt++;
        for (int c : adj[v])
            if (c != par[v] && c != heavy[v]) st.push_back(c);
    }
}

Bước 3: cây phân đoạn từ dưới lên. Mảng t[2n], lá $p$ ở ô $n + p$ . get thu hẹp nửa khoảng $[l, r + 1)$ từ hai phía, lấy ô lẻ ở đầu trái và ô trước ô lẻ ở đầu phải.

C++

void update(int p, int x) {
    for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
}

int get(int l, int r) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, t[l++]);
        if (r & 1) res = max(res, t[--r]);
    }
    return res;
}

Bước 4: đi trên đường. Khi $u$ , $v$ chưa cùng chuỗi, đầu chuỗi nào sâu hơn thì chuỗi đó chắc chắn không chứa LCA: lấy cả đoạn từ đầu chuỗi tới đỉnh đó rồi nhảy lên cha của đầu chuỗi. Khi đã cùng chuỗi, đỉnh nông hơn là LCA, lấy đoạn giữa hai đỉnh.

C++

int path(int u, int v) {
    int res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res = max(res, get(pos[head[u]], pos[u]));
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    return max(res, get(pos[u], pos[v]));
}

Vì sao chỉ $O(\log n)$ chuỗi: đi qua một cạnh nhẹ từ con lên cha thì kích thước cây con tăng ít nhất gấp đôi, vì con nhẹ không lớn hơn con nặng. Từ một đỉnh lên gốc chỉ qua tối đa $\log_2 n$ cạnh nhẹ.

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2e5 + 5;
int n, q, cnt, a[N], par[N], dep[N], sz[N], heavy[N], head[N], pos[N], t[2 * N];
vector<int> adj[N];

void build(int root) {
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, order.push_back(v);
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], p = par[u];
        sz[u]++;
        if (p) {
            sz[p] += sz[u];
            if (!heavy[p] || sz[u] > sz[heavy[p]]) heavy[p] = u;
        }
    }
    vector<int> st = {root};
    while (!st.empty()) {
        int h = st.back();
        st.pop_back();
        for (int v = h; v; v = heavy[v]) {
            head[v] = h, pos[v] = cnt++;
            for (int c : adj[v])
                if (c != par[v] && c != heavy[v]) st.push_back(c);
        }
    }
}

void update(int p, int x) {
    for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
}

int get(int l, int r) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, t[l++]);
        if (r & 1) res = max(res, t[--r]);
    }
    return res;
}

int path(int u, int v) {
    int res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res = max(res, get(pos[head[u]], pos[u]));
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    return max(res, get(pos[u], pos[v]));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    build(1);
    for (int i = 1; i <= n; i++) update(pos[i], a[i]);
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) update(pos[x], y);
        else cout << path(x, y) << '\n';
    }
}

Output7
4
9
4

Mỗi truy vấn $O(\log^2 n)$ . Phần $\log^2$ này gồm $\log n$ đoạn mỗi đường, mỗi đoạn một truy vấn cây phân đoạn. Hằng số của cây phân đoạn vì vậy quyết định tốc độ của cả bài:

Hai triệu truy vấn cực đại đoạn trên 200 nghìn phần tử, hai kiểu cây phân đoạn, đo trên i7-10850H, g++ -O2.

Cây phân đoạn viết từ dưới lên nhanh hơn bản đệ quy khoảng 2,7 lần. Quy tắc: không cần cập nhật lười thì dùng cây từ dưới lên, HLD sẽ nhanh gấp mấy lần.

Giá trị trên cạnh

Khi trọng số nằm trên cạnh, gán trọng số cạnh $(p, c)$ với $p$ là cha cho đỉnh con $c$ . Đường $u \to v$ gồm các cạnh ứng với mọi đỉnh trên đường trừ LCA. Ở bước cuối, khi $u, v$ cùng chuỗi và $u$ nông hơn, $u$ chính là LCA: chỉ lấy đoạn $[pos_u + 1, pos_v]$ , và bỏ qua nếu $u = v$ . Các bước nhảy trước đó giữ nguyên, vì đầu chuỗi được nhảy qua không phải LCA.

Hỏi nhanh

Trọng số đặt ở đỉnh con. Truy vấn đường $u \to v$ với LCA là $w \ne u, v$ . Vị trí nào phải bỏ khỏi kết quả?

Ví dụCạnh Lớn Nhất Trên Đường

Đề. $T \le 20$ cây, mỗi cây $n \le 10^4$ đỉnh, cạnh đánh số theo input. Lệnh QUERY u v in trọng số cạnh lớn nhất trên đường (0 nếu $u = v$ ), CHANGE i w đổi trọng số cạnh $i$ , DONE kết thúc cây.

Lời giải. Khung HLD y như ví dụ trước (build, update, get giống hệt), chỉ khác giá trị nằm trên cạnh. Gán cạnh $i$ cho đầu mút sâu hơn, tức đỉnh con. Đường $u \to v$ đi qua cạnh của mọi đỉnh trên đường trừ LCA, nên ở bước cuối bỏ vị trí của LCA.

Bước 1: đặt cạnh vào đỉnh con. Sau build(1), đổi chỗ để eu[i] luôn là đầu sâu hơn, rồi đặt trọng số vào pos[eu[i]]. Lệnh CHANGE i w vì vậy chỉ là update(pos[eu[i]], w).

C++

for (int i = 1; i < n; i++) {
    if (dep[eu[i]] < dep[ev[i]]) swap(eu[i], ev[i]);
    update(pos[eu[i]], ew[i]);
}

Bước 2: bỏ LCA. Vòng nhảy chuỗi giữ nguyên, vì đầu chuỗi được nhảy qua không bao giờ là LCA, nên cạnh từ nó lên cha nằm trên đường. Ở bước cuối $u$ là LCA, nên lấy $[pos_u + 1, pos_v]$ ; khi $u = v$ thì không còn cạnh nào và kết quả là 0.

C++

if (dep[u] > dep[v]) swap(u, v);
if (u != v) res = max(res, get(pos[u] + 1, pos[v]));

Bước 3: nhiều cây. Đầu mỗi cây: cnt = 0, xóa adj, par, dep, sz, heavy, và xóa t tới $2n$ . Quên xóa heavy thì con nặng của cây trước còn sót lại, chuỗi bị nối sai.

C++

cnt = 0;
for (int i = 0; i <= n; i++) adj[i].clear(), par[i] = dep[i] = sz[i] = heavy[i] = 0;
for (int i = 0; i < 2 * n; i++) t[i] = 0;

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e4 + 5;
int n, cnt, eu[N], ev[N], ew[N], par[N], dep[N], sz[N], heavy[N], head[N], pos[N], t[2 * N];
vector<int> adj[N];

void build(int root) {
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, order.push_back(v);
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], p = par[u];
        sz[u]++;
        if (p) {
            sz[p] += sz[u];
            if (!heavy[p] || sz[u] > sz[heavy[p]]) heavy[p] = u;
        }
    }
    vector<int> st = {root};
    while (!st.empty()) {
        int h = st.back();
        st.pop_back();
        for (int v = h; v; v = heavy[v]) {
            head[v] = h, pos[v] = cnt++;
            for (int c : adj[v])
                if (c != par[v] && c != heavy[v]) st.push_back(c);
        }
    }
}

void update(int p, int x) {
    for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
}

int get(int l, int r) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, t[l++]);
        if (r & 1) res = max(res, t[--r]);
    }
    return res;
}

int path(int u, int v) {
    int res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res = max(res, get(pos[head[u]], pos[u]));
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    if (u != v) res = max(res, get(pos[u] + 1, pos[v]));
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        cnt = 0;
        for (int i = 0; i <= n; i++) adj[i].clear(), par[i] = dep[i] = sz[i] = heavy[i] = 0;
        for (int i = 0; i < 2 * n; i++) t[i] = 0;
        for (int i = 1; i < n; i++) {
            cin >> eu[i] >> ev[i] >> ew[i];
            adj[eu[i]].push_back(ev[i]);
            adj[ev[i]].push_back(eu[i]);
        }
        build(1);
        for (int i = 1; i < n; i++) {
            if (dep[eu[i]] < dep[ev[i]]) swap(eu[i], ev[i]);
            update(pos[eu[i]], ew[i]);
        }
        string s;
        while (cin >> s && s != "DONE") {
            int x, y;
            cin >> x >> y;
            if (s == "QUERY") cout << path(x, y) << '\n';
            else update(pos[eu[x]], y);
        }
    }
}

Input1
5
1 2 4
1 3 7
3 4 2
3 5 6
QUERY 2 4
CHANGE 2 1
QUERY 2 4
CHANGE 3 9
QUERY 4 5
QUERY 1 1
DONE

Output7
4
9
0

Mỗi lệnh $O(\log^2 n)$ .

Đường và cây con

Cập nhật cả đoạn (cộng, gán) dùng cây phân đoạn có lan truyền lười; HLD chỉ quyết định đoạn nào cần cập nhật. Cách đánh số đi con nặng trước giữ cây con thành đoạn, nên một cây phân đoạn phục vụ được cả thao tác trên đường lẫn trên cây con, với cây con của $x$ là $[pos_x, pos_x + sz_x - 1]$ .

Ví dụCập Nhật Đường Và Cây Con

Đề. Cây $n \le 10^5$ đỉnh, gốc $r$ , $m \le 10^5$ thao tác: cộng $z$ trên đường $x \to y$ ; tổng trên đường; cộng $z$ vào cây con $x$ ; tổng cây con $x$ . Kết quả theo mô-đun $p \le 2^{30}$ .

Lời giải. Cùng một cách đánh số phục vụ cả đường lẫn cây con. Đường cắt thành các đoạn chuỗi như mọi bài HLD. Cây con của $x$ là đoạn $[pos_x, pos_x + sz_x - 1]$ , vì mọi đỉnh trong cây con của $x$ được đánh số liền nhau ngay sau $x$ . Cả bốn thao tác thành cộng đoạn và tổng đoạn trên một cây phân đoạn cộng lười. build như ví dụ đầu, dựng từ gốc root của đề.

Vì sao cây con là một đoạn: lấy $x$ trên một chuỗi. Các đỉnh dưới $x$ trên chuỗi được đánh số ngay sau $x$ . Con nhẹ của các đỉnh trên chuỗi được đẩy vào ngăn xếp theo thứ tự từ trên xuống, nên khi lấy ra thì đỉnh sâu hơn được xử lý trước, và mỗi con nhẹ được đánh số xong cả cây con của nó trước khi lấy phần tử cũ hơn trong ngăn xếp. Vậy ngay sau chuỗi là các cây con nhẹ của đỉnh sâu nhất, rồi của đỉnh trên nó, …, lên tới $x$ : mọi thứ thuộc cây con của $x$ nằm liền một khối.

Bước 1: cây phân đoạn cộng lười theo mô-đun. addNode cộng $v$ cho cả một nút: tổng tăng $v \cdot$ độ dài, nhãn lười tăng $v$ . Lượng cộng dưới $2^{30}$ nhân độ dài tới $10^5$ vẫn vừa long long.

C++

void addNode(int x, int l, int r, ll v) {
    sum[x] = (sum[x] + v * (r - l + 1)) % P;
    lz[x] = (lz[x] + v) % P;
}

void push(int x, int l, int r) {
    if (!lz[x]) return;
    int mid = (l + r) / 2;
    addNode(2 * x, l, mid, lz[x]);
    addNode(2 * x + 1, mid + 1, r, lz[x]);
    lz[x] = 0;
}

update và get là cộng đoạn, tổng đoạn chuẩn, gọi push trước khi xuống con. base[pos[i]] đặt giá trị ban đầu đúng chỗ trước khi init.

Bước 2: trên đường. Khuôn nhảy chuỗi của ví dụ đầu, thay cực đại bằng cộng đoạn (hay tổng đoạn).

C++

void pathAdd(int u, int v, ll z) {
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        update(1, 0, n - 1, pos[head[u]], pos[u], z);
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    update(1, 0, n - 1, pos[u], pos[v], z);
}

Bước 3: trên cây con. Gọi thẳng trên một đoạn.

C++

update(1, 0, n - 1, pos[x], pos[x] + sz[x] - 1, z % P);

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5;
int n, m, root, cnt, par[N], dep[N], sz[N], heavy[N], head[N], pos[N];
ll P, a[N], base[N], sum[4 * N], lz[4 * N];
vector<int> adj[N];

void build(int root) {
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, order.push_back(v);
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], p = par[u];
        sz[u]++;
        if (p) {
            sz[p] += sz[u];
            if (!heavy[p] || sz[u] > sz[heavy[p]]) heavy[p] = u;
        }
    }
    vector<int> st = {root};
    while (!st.empty()) {
        int h = st.back();
        st.pop_back();
        for (int v = h; v; v = heavy[v]) {
            head[v] = h, pos[v] = cnt++;
            for (int c : adj[v])
                if (c != par[v] && c != heavy[v]) st.push_back(c);
        }
    }
}

void addNode(int x, int l, int r, ll v) {
    sum[x] = (sum[x] + v * (r - l + 1)) % P;
    lz[x] = (lz[x] + v) % P;
}

void push(int x, int l, int r) {
    if (!lz[x]) return;
    int mid = (l + r) / 2;
    addNode(2 * x, l, mid, lz[x]);
    addNode(2 * x + 1, mid + 1, r, lz[x]);
    lz[x] = 0;
}

void init(int x, int l, int r) {
    if (l == r) {
        sum[x] = base[l];
        return;
    }
    int mid = (l + r) / 2;
    init(2 * x, l, mid);
    init(2 * x + 1, mid + 1, r);
    sum[x] = (sum[2 * x] + sum[2 * x + 1]) % P;
}

void update(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        addNode(x, l, r, v);
        return;
    }
    push(x, l, r);
    int mid = (l + r) / 2;
    update(2 * x, l, mid, ql, qr, v);
    update(2 * x + 1, mid + 1, r, ql, qr, v);
    sum[x] = (sum[2 * x] + sum[2 * x + 1]) % P;
}

ll get(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    push(x, l, r);
    int mid = (l + r) / 2;
    return (get(2 * x, l, mid, ql, qr) + get(2 * x + 1, mid + 1, r, ql, qr)) % P;
}

void pathAdd(int u, int v, ll z) {
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        update(1, 0, n - 1, pos[head[u]], pos[u], z);
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    update(1, 0, n - 1, pos[u], pos[v], z);
}

ll pathSum(int u, int v) {
    ll res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res += get(1, 0, n - 1, pos[head[u]], pos[u]);
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += get(1, 0, n - 1, pos[u], pos[v]);
    return res % P;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> root >> P;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    build(root);
    for (int i = 1; i <= n; i++) base[pos[i]] = a[i] % P;
    init(1, 0, n - 1);
    while (m--) {
        int type, x;
        ll y, z;
        cin >> type >> x;
        if (type == 1) {
            cin >> y >> z;
            pathAdd(x, y, z % P);
        } else if (type == 2) {
            cin >> y;
            cout << pathSum(x, y) << '\n';
        } else if (type == 3) {
            cin >> z;
            update(1, 0, n - 1, pos[x], pos[x] + sz[x] - 1, z % P);
        } else cout << get(1, 0, n - 1, pos[x], pos[x] + sz[x] - 1) << '\n';
    }
}

Input6 10 3 10
2 7 1 4 6 3
3 1
3 4
1 2
4 5
4 6
2 2 5
1 2 6 5
4 4
3 1 4
2 2 5
3 3 3
4 3
1 5 5 7
2 5 5
4 1

Output0
3
8
4
6
3

Thao tác đường $O(\log^2 n)$ , thao tác cây con $O(\log n)$ .

Không giao hoán

Cực đại hay tổng không quan tâm thứ tự, nhưng ghép hàm, nhân ma trận, đoạn con tổng lớn nhất thì có. Trên đường $u \to v$ , phần đi lên từ $u$ tới LCA đi theo chiều giảm của pos trong mỗi chuỗi, còn phần đi xuống tới $v$ theo chiều tăng.

Cây phân đoạn giữ hai giá trị cho mỗi nút: ghép trái sang phải và phải sang trái. Phía $u$ ghép ngay các đoạn theo thứ tự gặp. Phía $v$ gặp các đoạn theo thứ tự ngược với chiều đi, nên lưu lại rồi ghép từ cuối danh sách.

Cây phân đoạn từ dưới lên vẫn dùng được với phép không giao hoán, miễn khi truy vấn giữ riêng phần ghép bên trái và bên phải.

Ví dụGhép Hàm Trên Đường

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh, đỉnh $i$ mang hàm $f_i(x) = a_i x + b_i \bmod 998244353$ . $q \le 2 \cdot 10^5$ thao tác: đổi hàm tại một đỉnh; hoặc áp lần lượt các hàm trên đường từ $u$ tới $v$ vào $x$ và in kết quả.

Lời giải. Áp $f$ rồi $g$ cho $g(f(x)) = g_a (f_a x + f_b) + g_b$ , tức hàm $(g_a f_a,\ g_a f_b + g_b)$ . Phép ghép này không giao hoán, nên phải ghép đúng chiều đi. Trên một chuỗi, pos tăng khi đi xuống: đoạn đi lên từ $u$ đọc các vị trí theo chiều giảm, đoạn đi xuống tới $v$ đọc theo chiều tăng. Mỗi nút cây phân đoạn vì vậy lưu hai hàm: tl ghép từ vị trí nhỏ tới lớn, tr ghép từ lớn tới nhỏ. build như ví dụ đầu; đỉnh trong đề đánh số từ 0 nên dời lên 1.

Bước 1: ghép hai hàm. comb(x, y) là “áp x rồi áp y”; hàm đồng nhất là {1, 0}. pull cho tl ghép con trái rồi con phải, tr ghép con phải rồi con trái.

C++

F comb(F x, F y) {
    return {y.a * x.a % MOD, (y.a * x.b + y.b) % MOD};
}

void pull(int p) {
    tl[p] = comb(tl[2 * p], tl[2 * p + 1]);
    tr[p] = comb(tr[2 * p + 1], tr[2 * p]);
}

Bước 2: hỏi một đoạn theo chiều tăng. x gom các khối ở đầu trái theo đúng thứ tự gặp nên ghép vào sau x; y gom các khối ở đầu phải, khối mới gặp đứng trước các khối đã có nên ghép vào trước y. Kết quả là x rồi y.

C++

F getL(int l, int r) {
    F x = {1, 0}, y = {1, 0};
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) x = comb(x, tl[l++]);
        if (r & 1) y = comb(tl[--r], y);
    }
    return comb(x, y);
}

getR đối xứng với chiều giảm, dùng tr: khối đầu trái mới gặp có vị trí lớn hơn nên áp trước các khối trái đã có, khối đầu phải mới gặp áp sau; kết quả là phần phải rồi phần trái.

Bước 3: đi trên đường. up là hàm đã ghép xong của phần đi lên từ $u$ , mỗi đoạn chuỗi lấy bằng getR và nối ngay vào sau. Phần đi xuống tới $v$ được gặp theo thứ tự từ $v$ lên, ngược với chiều đi, nên gom vào down rồi ghép từ cuối danh sách. Ở bước cuối, $u$ sâu hơn thì đi lên tới $v$ (getR), ngược lại đi xuống (getL).

C++

while (head[u] != head[v]) {
    if (dep[head[u]] >= dep[head[v]]) {
        up = comb(up, getR(pos[head[u]], pos[u]));
        u = par[head[u]];
    } else {
        down.push_back(getL(pos[head[v]], pos[v]));
        v = par[head[v]];
    }
}
if (dep[u] >= dep[v]) up = comb(up, getR(pos[v], pos[u]));
else up = comb(up, getL(pos[u], pos[v]));
for (int i = (int)down.size() - 1; i >= 0; i--) up = comb(up, down[i]);

Bước 4: dựng và sửa. Đặt lá rồi pull từ $n - 1$ về 1. Đổi hàm tại một đỉnh: sửa lá rồi pull ngược lên gốc.

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2e5 + 5;
const ll MOD = 998244353;
struct F {
    ll a, b;
};
int n, q, cnt, par[N], dep[N], sz[N], heavy[N], head[N], pos[N];
F f[N], tl[2 * N], tr[2 * N];
vector<int> adj[N];

F comb(F x, F y) {
    return {y.a * x.a % MOD, (y.a * x.b + y.b) % MOD};
}

void build(int root) {
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, order.push_back(v);
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], p = par[u];
        sz[u]++;
        if (p) {
            sz[p] += sz[u];
            if (!heavy[p] || sz[u] > sz[heavy[p]]) heavy[p] = u;
        }
    }
    vector<int> st = {root};
    while (!st.empty()) {
        int h = st.back();
        st.pop_back();
        for (int v = h; v; v = heavy[v]) {
            head[v] = h, pos[v] = cnt++;
            for (int c : adj[v])
                if (c != par[v] && c != heavy[v]) st.push_back(c);
        }
    }
}

void pull(int p) {
    tl[p] = comb(tl[2 * p], tl[2 * p + 1]);
    tr[p] = comb(tr[2 * p + 1], tr[2 * p]);
}

F getL(int l, int r) {
    F x = {1, 0}, y = {1, 0};
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) x = comb(x, tl[l++]);
        if (r & 1) y = comb(tl[--r], y);
    }
    return comb(x, y);
}

F getR(int l, int r) {
    F x = {1, 0}, y = {1, 0};
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) x = comb(tr[l++], x);
        if (r & 1) y = comb(y, tr[--r]);
    }
    return comb(y, x);
}

ll path(int u, int v, ll x) {
    F up = {1, 0};
    vector<F> down;
    while (head[u] != head[v]) {
        if (dep[head[u]] >= dep[head[v]]) {
            up = comb(up, getR(pos[head[u]], pos[u]));
            u = par[head[u]];
        } else {
            down.push_back(getL(pos[head[v]], pos[v]));
            v = par[head[v]];
        }
    }
    if (dep[u] >= dep[v]) up = comb(up, getR(pos[v], pos[u]));
    else up = comb(up, getL(pos[u], pos[v]));
    for (int i = (int)down.size() - 1; i >= 0; i--) up = comb(up, down[i]);
    return (up.a * x + up.b) % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> f[i].a >> f[i].b;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u++, v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    build(1);
    for (int i = 1; i <= n; i++) tl[n + pos[i]] = tr[n + pos[i]] = f[i];
    for (int p = n - 1; p >= 1; p--) pull(p);
    while (q--) {
        int type;
        ll x, y, z;
        cin >> type >> x >> y >> z;
        if (type == 0) {
            int p = n + pos[x + 1];
            tl[p] = tr[p] = {y, z};
            for (p >>= 1; p; p >>= 1) pull(p);
        } else cout << path(x + 1, y + 1, z) << '\n';
    }
}

Output29
80
23
14
61
10

Mỗi thao tác $O(\log^2 n)$ .

Khi đi thi

Truy vấn, cập nhật trên đường cây với phép quen thuộc (tổng, cực đại, gán, cộng): HLD cùng cây phân đoạn, $O(\log^2 n)$ mỗi thao tác. Dựng bằng BFS và ngăn xếp để khỏi tràn ngăn xếp gọi hàm.
Trọng số trên cạnh: đặt vào đỉnh con, bỏ vị trí LCA ở bước cuối. Cây con là $[pos_x, pos_x + sz_x - 1]$ .
Phép không giao hoán: mỗi nút lưu hai chiều ghép; phía $u$ ghép ngay, phía $v$ gom lại rồi ghép ngược.

Tóm tắt

Con nặng là con có cây con lớn nhất; mỗi cạnh nhẹ làm cây con giảm ít nhất một nửa, nên đường lên gốc qua tối đa $\log n$ chuỗi.
Đánh số liên tiếp theo chuỗi và theo DFS đi con nặng trước: chuỗi và cây con đều là đoạn.
Truy vấn đường: nhảy đầu chuỗi sâu hơn cho tới khi cùng chuỗi, mỗi lần một đoạn.
Giá trị cạnh đặt ở đỉnh con; phép không giao hoán cần ghép theo đúng chiều đi.

Bài tập

Tổng Giá Trị Trên Lộ Trìnhcanuc80k5802

LQDOJ

Đỉnh Đánh Dấu Gần Gốccanuc80k5804

LQDOJ

Cộng Điểm, Hỏi Tổng Đườngcanuc80k5805

LQDOJ

Lượt Đi Qua Cạnhcanuc80k5806

LQDOJ

Điều Chỉnh Trên Lộ Trìnhcanuc80k5807

LQDOJ

Tổ Tiên Đã Đánh Dấucanuc80k5809

LQDOJ

Thống Kê Trên Đườngcanuc80k5810

LQDOJ

XOR Trên Câycanuc80k5811

LQDOJ

Cài Đặt Phụ Thuộccanuc80k5812

LQDOJ

Tích Lũy Trong Cây Concanuc80k5813

LQDOJ

Các Đoạn Màucanuc80k5814

LQDOJ

Đảo Dấu Trọng Sốcanuc80k5817

LQDOJ

Gán Đường Và Đoạn Tốt Nhấtcanuc80k5819

LQDOJ

Mạng Cạnh Tạm Khóacanuc80k5820

LQDOJ

Cây Con Theo Gốc Độngcanuc80k5822

LQDOJ

Khôi Phục Trọng Số Cạnhcanuc80k5823

LQDOJ

Heavy Light Decomposition

Chuỗi nặng

Ví dụGiá Trị Lớn Nhất Trên Đường

Giá trị trên cạnh

Ví dụCạnh Lớn Nhất Trên Đường

Đường và cây con

Ví dụCập Nhật Đường Và Cây Con

Không giao hoán

Ví dụGhép Hàm Trên Đường

Khi đi thi

Tóm tắt

Bài tập

Đọc thêm