Phần phân tích thuật toán root decomposition sẽ không được trình bày ở đây, tập trung vào chi tiết code:

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

const int MAXN = 50005;
const int MAXM = 200005;
const int LOG = 17;

int n, m, queryCount;

inline int fastRead() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

// Cấu trúc cạnh
struct EdgeInfo {
    int from, to, weight;
    bool operator<(const EdgeInfo& other) const {
        return weight < other.weight;
    }
} edges[MAXM];

// Union-Find cho MST
int parent[MAXN];
int findRoot(int x) {
    return parent[x] == x ? x : (parent[x] = findRoot(parent[x]));
}

// Lưu cây MST
vector<pair<int,int>> treeAdj[MAXN];

void addTreeEdge(int u, int v, int w) {
    treeAdj[u].push_back({v, w});
    treeAdj[v].push_back({u, w});
}

// Khởi tạo cây khung nhỏ nhất
void buildMST() {
    for (int i = 1; i <= n; i++) parent[i] = i;
    int edgeCount = 0;
    for (int i = 1; i <= m; i++) {
        int a = edges[i].from;
        int b = edges[i].to;
        int ra = findRoot(a);
        int rb = findRoot(b);
        if (ra != rb) {
            addTreeEdge(a, b, edges[i].weight);
            parent[ra] = rb;
            if (++edgeCount == n - 1) return;
        }
    }
}

// LCA preprocessing
int up[MAXN][LOG];
int maxW[MAXN][LOG];
int depth[MAXN];

void dfs(int node, int father) {
    for (auto [v, w] : treeAdj[node]) {
        if (v == father) continue;
        depth[v] = depth[node] + 1;
        up[v][0] = node;
        maxW[v][0] = w;
        for (int j = 1; j <= LOG - 1; j++) {
            up[v][j] = up[up[v][j-1]][j-1];
            maxW[v][j] = max(maxW[v][j-1], maxW[up[v][j-1]][j-1]);
        }
        dfs(v, node);
    }
}

void initLCA() {
    depth[1] = 1;
    dfs(1, 0);
}

// Tìm cạnh lớn nhất trên đường đi
int queryMaxWeight(int a, int b) {
    int result = -1;
    if (depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for (int i = LOG - 1, bit = 0; diff > 0; diff >>= 1, bit++) {
        if (diff & 1) {
            result = max(result, maxW[a][bit]);
            a = up[a][bit];
        }
    }
    if (a == b) return result;
    for (int i = LOG - 1; i >= 0; i--) {
        if (up[a][i] != up[b][i]) {
            result = max(result, maxW[a][i]);
            result = max(result, maxW[b][i]);
            a = up[a][i];
            b = up[b][i];
        }
    }
    result = max(result, max(maxW[a][0], maxW[b][0]));
    return result;
}

// Cấu trúc query
struct QueryItem {
    int l, r, k, c, idx;
    bool operator<(const QueryItem& other) const {
        if (k != other.k) return k < other.k;
        return c < other.c;
    }
} queries[MAXN];

// Segment tree
struct SegmentNode {
    int left, right, maximum;
} segTree[MAXN * 4];

int segData[MAXN];

void buildSeg(int node, int l, int r) {
    segTree[node].left = l;
    segTree[node].right = r;
    if (l == r) {
        segTree[node].maximum = segData[l];
        return;
    }
    int mid = (l + r) >> 1;
    buildSeg(node << 1, l, mid);
    buildSeg(node << 1 | 1, mid + 1, r);
    segTree[node].maximum = max(segTree[node << 1].maximum, 
                                 segTree[node << 1 | 1].maximum);
}

int querySeg(int node, int l, int r) {
    if (segTree[node].left >= l && segTree[node].right <= r)
        return segTree[node].maximum;
    int mid = (segTree[node].left + segTree[node].right) >> 1;
    int ans = -1;
    if (l <= mid) ans = querySeg(node << 1, l, r);
    if (r > mid) ans = max(ans, querySeg(node << 1 | 1, l, r));
    return ans;
}

// Xử lý query nhỏ
void prepareSmall(QueryItem& q) {
    int L = 0, R = n, cnt = 0;
    for (int i = L / q.k * q.k + q.c; i + q.k <= R; i += q.k) {
        if (i < L) continue;
        segData[++cnt] = queryMaxWeight(i, i + q.k);
    }
    buildSeg(1, 1, cnt);
}

int solveSmall(QueryItem& q, bool changed) {
    if (changed) prepareSmall(q);
    int L = q.l, R = q.r;
    int k = q.k, c = q.c;
    int offset = 1 + ((L - c) % k != 0);
    int leftPos = (L - c) / k + offset;
    if (L <= c) leftPos = 1;
    int rightPos = (R - c) / k;
    return querySeg(1, leftPos, rightPos);
}

int solveLarge(QueryItem& q) {
    int L = q.l, R = q.r, ans = -1;
    for (int i = L / q.k * q.k + q.c; i + q.k <= R; i += q.k) {
        if (i < L) continue;
        ans = max(ans, queryMaxWeight(i, i + q.k));
    }
    return ans;
}

int main() {
    n = fastRead();
    m = fastRead();
    queryCount = fastRead();
    
    for (int i = 1; i <= m; i++) {
        edges[i].from = fastRead();
        edges[i].to = fastRead();
        edges[i].weight = fastRead();
    }
    
    sort(edges + 1, edges + m + 1);
    buildMST();
    initLCA();
    
    int answer[MAXN];
    for (int i = 1; i <= queryCount; i++) {
        queries[i].l = fastRead();
        queries[i].r = fastRead();
        queries[i].k = fastRead();
        queries[i].c = fastRead();
        queries[i].idx = i;
    }
    
    sort(queries + 1, queries + queryCount + 1);
    
    int threshold = min(n / 3, 110);
    int prevK = 0, prevC = 0;
    
    for (int i = 1; i <= queryCount; i++) {
        if (queries[i].k > threshold) {
            answer[queries[i].idx] = solveLarge(queries[i]);
            continue;
        }
        bool changed = false;
        if (prevK != queries[i].k) {
            prevK = queries[i].k;
            changed = true;
        }
        if (prevC != queries[i].c) {
            prevC = queries[i].c;
            changed = true;
        }
        answer[queries[i].idx] = solveSmall(queries[i], changed);
    }
    
    for (int i = 1; i <= queryCount; i++)
        printf("%d\n", answer[i]);
    return 0;
}

Tại sao code ban đầu bị TLE:

Việc sử dụng toán tử so sánh để sắp xếp các truy vấn theo lý thuyết sẽ nhóm các truy vấn có cùng giá trị k và c lại với nhau. Chiến lược sắp xếp này ưu tiên theo k trước, sau đó mới đến c. Mục đích là để nhóm các truy vấn có tham số giống nhau, từ đó có thể xử lý một lần và giảm thiểu việc khởi tạo lặp đi lặp lại. Đoạn code bạn cung cấp:

bool operator<(const QueryItem& other) const {
    return k < other.k;
    if (k == other.k)
        return c < other.c;
}

Tuy nhiên, toán tử < ở trên có một lỗi logic nghiêm trọng. Nếu k < other.k là true, hàm sẽ kết thúc ngay tại đó, đó là đúng. Nhưng nếu k == other.k, bạn muốn tiếp tục so sánh giá trị của c. Tuy nhiên, vì có câu lệnh return k < other.k; ở đó, khi k bằng other.k, hàm sẽ kết thúc ngay lập tức và câu lệnh if (k == other.k) phía sau sẽ không bao giờ được thực thi.

Cách viết đúng:

bool operator<(const QueryItem& other) const {
    if (k != other.k) return k < other.k;
    return c < other.c;
}

Hoặc viết ngắn gọn hơn:

bool operator<(const QueryItem& other) const {
    return k == other.k ? c < other.c : k < other.k;
}

Cách này đảm bảo khi k bằng nhau, sẽ so sánh theo giá trị của c, đảm bảo các truy vấn có cùng k và c được nhóm lại với nhau.

Nếu bạn đã implement đúng logic sắp xếp, mỗi khi gặp cặp (k, c) khác nhau sẽ chỉ khởi tạo một lần duy nhất. Nếu vẫn xảy ra việc khởi tạo nhiều lần, cần kiểm tra kỹ logic để xác nhận mỗi cặp chỉ được xử lý một lần, và các truy vấn sau khi sắp xếp có được nhóm đúng như mong đợi hay không. Hãy xác nhận prepareSmall và các xử lý liên quan có bị giới hạn đúng trên từng cặp (k, c) duy nhất không.

Tóm lại, việc implement và áp dụng đúng logic sắp xếp là rất quan trọng, đảm bảo các truy vấn được tổ chức và xử lý theo cách mong muốn, tránh các thao tác lặp đi lặp lại không cần thiết.

Vấn đề cốt lõi nằm ở việc sử dụng return trực tiếp - nếu k != other.k, hàm sẽ trả về false ngay lập tức, nhưng phần so sánh c phía sau sẽ không bao giờ được thực thi.