Олимпијада (мои '16)

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,O3,Ofast,unroll-loops")

const int N = 107308, inf = 1797710308;
int n, L, H, s;
vector <pair <int, int>> g[N];
int sgt[3 * N], subtsize[N];
bool resetsgt[3 * N], visited[N];

void sgtupdate(int q, int val, int node, int cl, int cr) {
    if (q < cl || cr < q) return;
    if (resetsgt[node]) {
        if (node < s) resetsgt[2 * node + 1] = resetsgt[2 * node + 2] = true;
        sgt[node] = -inf;
        resetsgt[node] = false;
    }
    if (q == cl && q == cr) {
        sgt[node] = max(sgt[node], val);
        return;
    }
    int cm = cl + cr >> 1;
    sgtupdate(q, val, 2 * node + 1, cl, cm);
    sgtupdate(q, val, 2 * node + 2, cm + 1, cr);
    sgt[node] = max(resetsgt[2 * node + 1] ? -inf : sgt[2 * node + 1], resetsgt[2 * node + 2] ? -inf : sgt[2 * node + 2]);
}
int sgtget(int ql, int qr, int node, int cl, int cr) {
    if (qr < cl || cr < ql) return -inf;
    if (resetsgt[node]) return -inf;
    if (ql <= cl && cr <= qr) return sgt[node];
    int cm = cl + cr >> 1;
    return max(sgtget(ql, qr, 2 * node + 1, cl, cm), sgtget(ql, qr, 2 * node + 2, cm + 1, cr));
}
int &calcsubt(const int &node, const int &parent) {
    subtsize[node] = 1;
    for (auto &[neigh, _] : g[node]) {
        if (visited[neigh] || neigh == parent) continue;
        subtsize[node] += calcsubt(neigh, node);
    }
    return subtsize[node];
}
bool querydfs(const int &node, const int &parent, const int &depth, const int &val, const int &median) {
    if (sgtget(L - depth, H - depth, 0, 0, s) + val >= 0) {
        // cerr << "FOUND IT!\n";
        return true; // NAJDOVME!! se vrakame do binary searchot
    }
    for (auto &[child, w] : g[node]) {
        if (child == parent || visited[child]) continue;
        if (querydfs(child, node, depth + 1, val + (w >= median ? 1 : -1), median)) return true;
    }
    return false;
}
void updatedfs(const int &node, const int &parent, const int &depth, const int &val, const int &median) {
    sgtupdate(depth, val, 0, 0, s);
    for (auto &[child, w] : g[node]) {
        if (child == parent || visited[child]) continue;
        updatedfs(child, node, depth + 1, val + (w >= median ? 1 : -1), median);
    }
}
pair <int, int> findcentroid(int node) {
    int sz = subtsize[node] / 2, parent = -1;
    bool cont = true;
    while (cont) {
        cont = false;
        for (auto &[neigh, _] : g[node]) {
            if (!visited[neigh] && neigh != parent && subtsize[neigh] > sz) {
                cont = true;
                parent = node;
                node = neigh;
                break;
            }
        }
    }
    return {node, parent};
}
bool searchpath(const int &root, const int &median) {
    if (visited[root]) return false;
    auto [centroid, centparent] = findcentroid(root);
    visited[centroid] = true;
    resetsgt[0] = true;
    sgtupdate(0, 0, 0, 0, s);
    for (auto &[neigh, w] : g[centroid]) {
        if (visited[neigh]) continue;
        if (querydfs(neigh, centroid, 1, w >= median ? 1 : -1, median)) {
            // cerr << "FOUND!! " << centroid << ' ' << neigh << ' ' << median << '\n';
            return true;
        }
        updatedfs(neigh, centroid, 1, w >= median ? 1 : -1, median);
    }
    if (centparent >= 0) calcsubt(centparent, -1);
    for (auto &[neigh, _] : g[centroid]) {
        if (searchpath(neigh, median)) return true;
    }
    return false;
}
// Dali postoi pat so medijana >= median
bool ok(int median) {
    memset(visited, 0, n * sizeof(bool));
    calcsubt(0, -1);
    return searchpath(0, median);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> L >> H;
    s = (1 << int(ceil(log2(n + 5)))) - 1;
    for (int i = 1, a, b, w; i < n; i++) {
        cin >> a >> b >> w;
        g[--a].push_back({--b, w});
        g[b].push_back({a, w});
    }
    int l = 0, r = 15e8, m;
        while (r - l > 1) {
        m = l + r >> 1;
        if (ok(m)) l = m;
        else r = m;
    }
    // cerr << l << ' ' << r;
    cout << (l != r && ok(r) ? r : l);
}