Trường hợp đường đi đơn không đi qua cạnh thêm vào có thể dễ dàng được xử lý trong ~O(n^2)~. Ta xét trường hợp đường đi đơn có đi qua cạnh được thêm vào.

Ta gọi ~2~ đỉnh mà cạnh mới nối vào là ~(x, y)~, và trọng số cạnh này là ~w (l \le w \le r)~. Ngoài ra, ta định nghĩa ~d(x, y)~ là tổng trọng số các cạnh trên đường đi ngắn nhất từ ~x~ đến ~y~, và ~pref(i) = d(1, i)~. Ta chứng minh được ~d(x, y)~ = ~pref(x)~ ^ ~pref(y)~

Một đường đi từ ~u~ đến ~v~ ~(1 \le u, v \le n)~ và đi qua cạnh khi đó sẽ có dạng ~u \to x \to y \to v~ và có tổng trọng số là ~(d(u, x)~ ^ ~w~ ^ ~d(y, v))~ = ~(pref(u)~ ^ ~pref(x)~ ^ ~w~ ^ ~pref(y)~ ^ ~pref(v))~.

Ngoài ra ta nhận thấy rằng để đường đi ~u \to x \to y \to v~ là đường đi đơn, thì ~u \to x~ và ~y \to v~ phải không giao nhau tại điểm nào. Hay nói cách khác, tồn tại một cạnh ~(a, b)~ sao cho

• ~a~ là cha của ~b~ (1)

• Khi bỏ cạnh ~(a, b)~ ra khỏi cây, cây sẽ bị chia ra làm ~2~ thành phần liên thông. Khi đó ~u \to x~ và ~v \to w~ nằm ở ~2~ phần khác nhau. Điều này có nghĩa là trong ~(u \to x)~ và ~(v \to w)~ sẽ có một đường đi nằm hoàn toàn trong subtree của ~b~, và đường đi còn lại sẽ nằm hoàn toàn ngoài subtree của ~b~. (2)

Ta sẽ duyệt qua tất cả các cạnh ~(a, b)~ trong cây, và tìm ra ~4~ đỉnh ~u, x, y, v~ thỏa mãn điều kiện (2) sao cho ~(pref(u)~ ^ ~pref(x)~ ^ ~w~ ^ ~pref(y)~ ^ ~pref(v))~ lớn nhất có thể.

Đầu tiên, ta giải bài toán với ~w~ bất kì (đây cũng là subtask ~4~ của bài).

• Với mỗi cạnh ~(a, b)~ như trên, ta duyệt qua tất cả các cặp ~(u, x)~ có thể. Để giảm độ phức tạp, ta chỉ duyệt qua các cặp ~(u, x)~ sao cho ~lca(u, x) = b~ thay vì duyệt qua tất cả các cặp ~(u, x)~ có thể. Điều này giúp chúng ta xét mỗi cặp đỉnh trong cây chỉ ~1~ lần, và do đó tổng số cặp chúng ta xét trong cây chỉ là ~O(n^2)~.

• Với mỗi cặp ~(u, x)~, ta sẽ tìm cặp ~(v, w)~ tương ứng sao cho ~(pref(u)~ ^ ~pref(x)~ ^ ~w~ ^ ~pref(y)~ ^ ~pref(v))~ lớn nhất có thể. Đây là một bài toán sử dụng trie khá cơ bản.

Tuy nhiên ta gặp phải một vấn đề lớn - làm thế nào để duy trì được cây trie chứa ~pref(y)~ ^ ~pref(v)~ với mọi ~(v, y)~ thỏa mãn ~v~ và ~y~ nằm ngoài cây con của ~b~.

Để giải quyết vấn đề này, với mỗi đỉnh ~b~ ta sẽ lưu cây trie chứa những cặp ~(y, v)~ không thỏa mãn điều kiện trên, có nghĩa là có ít nhất ~1~ trong ~2~ đỉnh ~y~ hoặc ~v~ nằm trong cây con của ~b~. Ta nhận thấy có ~O(sz[b] * N)~ cặp như vậy với ~sz[b]~ là số đỉnh (tính cả ~b~) của cây con gốc ~b~.

• Ban đầu, ta lưu với mỗi đỉnh ~b~ trên đồ thị tất cả các cặp ~(b, v)~, với ~1 \le v \le n, v \neq b~

• Khi dfs đến đỉnh ~b~, ta xét những đỉnh con ~c~ của ~b~ trước. Khi đó với mỗi đỉnh ~c~, ta đang lưu những cặp thỏa mãn ít nhất 1 trong 2 đỉnh nằm trong cây con gốc ~c~. Ta sẽ

  • Merge những cây trie này với nhau sử dụng DSU.

  • Xóa đi những cặp đỉnh ~(y, v)~ xuất hiện nhiều lần.

Ta chứng minh rằng độ phức tạp của việc merge các trie vào với nhau là ~O(N^2 * 64)~.

Khi bắt đầu, chúng ta thực hiện thao tác thêm vào trie ~O(N^2)~ lần, và do đó tổng số đỉnh là ~O(N^2 * 64)~

Ta có thuật toán để merge ~2~ cây trie lại với nhau như sau:

Node* merge(Node* u, Node* v) {//Hiện tại ta đang ở node u và v
    if (!u->cnt) {// Nếu u rỗng thì ta đặt node sau khi merge = v
        return v;
    }
    if (!v->cnt) {// Nếu v rỗng thì ta đặt node sau khi merge = u
        return u;
    }
    //tạo ra node mới và tiếp tục merge 2 con 
    u->cnt += v->cnt;
    for (int b = 0; b < 2; b++) {
        u->ch[b] = merge(u->ch[b], v->ch[b]);
    }
    return u;
}

Ta thấy rằng để qua được ~2~ trường hợp if đầu tiên, thì ~2~ node đều không được phép rỗng. Điều này có nghĩa là ta đã "xóa" node ~v~, và tổng số node giữa tất cả các trie bị giảm đi ~1~. Do đó, số lần ta qua được ~2~ trường hợp if đầu tiên sẽ là ~O(N^2 * log_2(MAX))~.

Vậy còn số lần không qua được ~2~ trường hợp if đầu tiên thì sao? Để hàm ~merge(u, v)~ được gọi, cả ~par(u)~ và ~par(v)~ đều không được phép rỗng (~par(u)~ ở đây là đỉnh cha của ~u~, và tương tự với ~v~). Tuy nhiên với mỗi cặp node ~(u, v)~ không rỗng, thì ta chỉ gọi thêm ~2~ hàm. Điều này có nghĩa là số lần không qua được ~2~ trường hợp if đầu tiên cũng chỉ là ~O(N^2 * log_2(MAX))~

Ngoài ra, tổng số lần truy vấn trie là ~O(N^2)~ như đã nói ở trên

~\to~ Tổng đpt là ~O(N^2 * log_2(MAX))~ với MAX là giới hạn của ~a_i~.

Để giải bài toán một cách hiệu quả cho đoạn ~[l, r]~ và cặp ~(x, u)~, ta làm như sau:

• Đầu tiên, ta có một số định nghĩa:

  • ~cnt(a)~ là số cặp được lưu trong node ~a~ của trie

  • ~child(a)(0)~ và ~child(a)(1)~ là ~2~ con của node ~a~

• Ta duyệt qua các bit từ ~log_2(MAX) - 1~ về ~0~.

• Ta sẽ bò trên cả ~2~ cây trie - cây chứa tất cả các cặp xor (có ~\frac{N * (N - 1)}{2}~ cặp như vậy), và cây chứa các cặp ~(y, v)~ không thỏa mãn.

• Giả sử ta đang ở bit thứ ~i~, và ~2~ node chúng ta đang xét trong ~2~ cây trie là ~a~ và ~b~. Để xét xem có cặp ~(y, v)~ nào thỏa mãn có bit thứ ~i~ bằng ~0~ hay không, chúng ta kiểm tra xem liệu ~cnt(child(a)(0)) = cnt(child(b)(0))~ hay không.

• Gọi ~i~ là số lớn nhất sao cho bit thứ ~i~ của ~l~ và ~r~ khác nhau. Khi đó ta xử lý các bit ~> i~ như bình thường và chia ~[l, r]~ ra thành ~2~ đoạn ~[l, x]~ và ~[x + 1, r]~ với ~r = l | (2^i - 1)~

• Giả sử chúng ta đang xét đoạn ~[l, x]~ (đoạn ~[x + 1, r]~ có thể được xử lý tương tự). Ta for các bit ~j~ từ ~i~ về ~0~. Gọi ~cur~ là đáp án lớn nhất hiện tại.

  • Nếu ~j < i~ và bit thứ ~j~ của ~l~ ~= 0~, điều đó có nghĩa là ~(x - 2^j + 1) \ge i~, và đoạn ~[x - 2^j + 1, x]~ sẽ bao hết tất cả các khả năng có thể của ~(j - 1)~ bit cuối.

  • Nếu tồn tại ~1~ số thỏa mãn bit thứ ~j~ của số đó ~= 0~, thì chúng ta đã tìm được phương án tốt nhất. Chúng ta cập nhật ~cur + 2^j - 1~ vào đáp án.

  • Nếu không thì chúng ta cập nhật ~cur + 2^{(j - 1)} - 1~ vào đáp án, đặt ~a = child(a)(1), b = child(b)(1)~ và tiếp tục tìm kiếm

  • Nếu bit thứ ~j~ của ~l~ ~= 1~, chúng ta sẽ tìm kiếm xem có số nào thỏa mãn bit thứ ~j~ của số đó ~= 0~ không, và nếu có thì cộng ~2^j~ vào ~cur~ và đặt ~a = child(a)(0), b = child(b)(0)~.

  • Nếu không có số nào thỏa mãn thì ta đặt ~a = child(a)(1), b = child(b)(1)~

Với cách làm như trên, ta có thể tìm với mỗi cặp ~(u, x)~ cặp ~(y, v)~ tương ứng trong ~O(log_2(MAX))~. Tổng độ phức tạp của thuật toán trên sẽ là ~O(N^2 * log_2(MAX))~

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int LOG = 62;
const int N = 705;

static char buf[1000 << 20];

template <class X, class Y>
bool maximize(X& x, const Y& y) {
    return x < y ? x = y, 1 : 0;
}

void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i -= s];
}

void operator delete(void*) {}

struct Node {
    Node* ch[2];
    int cnt;

    Node() : cnt(0) { ch[0] = ch[1] = (Node*)buf; }
};

void modify(Node* u, ll x, int v) {
    u->cnt += v;
    for (int k = LOG; k >= 0; k--) {
        int b = (x >> k) & 1;
        if (!u->ch[b]->cnt) {
            u->ch[b] = new Node();
        }
        u = u->ch[b];
        u->cnt += v;
    }
}

Node* merge(Node* u, Node* v) {
    if (!u->cnt) {
        return v;
    }
    if (!v->cnt) {
        return u;
    }
    u->cnt += v->cnt;
    for (int b = 0; b < 2; b++) {
        u->ch[b] = merge(u->ch[b], v->ch[b]);
    }
    return u;
}

ll query(Node* u, Node* v, ll l, ll r, ll x, int k) {
    if (k < 0) {
        return 0;
    }
    assert(u->cnt > v->cnt);
    ll all = (1ll << (k + 1)) - 1;
    if (r - l == all) {
        return all;
    }
    int b = (l ^ x) >> k & 1;
    ll m = l | ((1ll << k) - 1);
    if (m < r) {
        Node *ul = u->ch[b], *vl = v->ch[b];
        ll res = 0;
        if (ul->cnt > vl->cnt) {
            maximize(res, query(ul, vl, m + 1, r, x, k - 1));
        }
        Node *ur = u->ch[b ^ 1], *vr = v->ch[b ^ 1];
        if (ur->cnt > vr->cnt) {
            maximize(res, query(ur, vr, l, m, x, k - 1));
        }
        return res | (1ll << k);
    } else {
        Node *ur = u->ch[b ^ 1], *vr = v->ch[b ^ 1];
        if (ur->cnt > vr->cnt) {
            return query(ur, vr, l, r, x, k - 1) | (1ll << k);
        } else {
            return query(u->ch[b], v->ch[b], l, r, x, k - 1);
        }
    }
}

vector<pair<int, ll>> adj[N];
Node *root[N], *all;
ll pref[N], res, l, r;
int n, tin[N], tout[N];
vector<int> tour;

void dfs_tour(int u, int p) {
    tin[u] = tour.size();
    tour.push_back(u);
    for (auto [v, w] : adj[u]) {
        if (v == p) {
            continue;
        }
        pref[v] = pref[u] ^ w;
        dfs_tour(v, u);
    }
    tout[u] = tour.size();
}

void dfs_solve(int u, int p) {
    root[u] = new Node();
    for (int v = 0; v < n; v++) {
        modify(root[u], pref[u] ^ pref[v], 1);
    }
    for (auto [v, w] : adj[u]) {
        if (v == p) {
            continue;
        }
        dfs_solve(v, u);
        root[u] = merge(root[u], root[v]);
    }
    if (!u) {
        return;
    }
    /// Remove duplicates
    for (auto [v, w] : adj[u]) {
        if (v == p) {
            continue;
        }
        for (int i = tin[v]; i < tout[v]; i++) {
            for (int j = tin[u]; j < tin[v]; j++) {
                modify(root[u], pref[tour[i]] ^ pref[tour[j]], -1);
            }
        }
    }
    maximize(res, query(all, root[u], l, r, 0, LOG));
    for (auto [v, w] : adj[u]) {
        if (v == p) {
            continue;
        }
        for (int i = tin[v]; i < tout[v]; i++) {
            for (int j = tin[u]; j < tin[v]; j++) {
                maximize(res, query(all, root[u], l, r,
                                    pref[tour[i]] ^ pref[tour[j]], LOG));
            }
        }
    }
}

void solve() {
    cin >> n >> l >> r;
    res = 0;
    tour.clear();
    all = new Node();
    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs_tour(0, -1);
    for (int u = 0; u < n; u++) {
        for (int v = u; v < n; v++) {
            modify(all, pref[u] ^ pref[v], 1);
            maximize(res, pref[u] ^ pref[v]);
        }
    }
    dfs_solve(0, -1);
    cout << res << '\n';
}

void init() {
    cin.tie(0)->sync_with_stdio(0);
    freopen("xtree.inp", "r", stdin);
    freopen("xtree.out", "w", stdout);
    Node* null = (Node*)buf;
    null->ch[0] = null->ch[1] = null;
    null->cnt = 0;
}

int main() {
    init();
    solve();
}