import math
def solve(n, treasures):
    t = treasures
    s = sum(v for _, v in t)
    trg = math.ceil(s / 2)
    t.sort()
    c = 0
    m = float('inf')
    left = 0
    for right in range(n):
        c += t[right][1]
        while c >= trg:
            m = min(m, t[right][0] - t[left][0] + 1)
            c -= t[left][1]
            left += 1
    return m  

Teasure division

#include <bits/stdc++.h>
using namespace std;
vector<int> solve(int node, int n, unordered_map<int, vector<pair<int, int>>>& h) {
    vector<int> dist(n + 1, INT_MAX);
    unordered_set<int> visited;
    dist[node] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, node});
    while (!q.empty()) {
        int val, currNode;
        tie(val, currNode) = q.top();
        q.pop();
        if (visited.find(currNode) != visited.end()) continue; 
        visited.insert(currNode);
        dist[currNode] = val;
        for (const auto& edge : h[currNode]) {
            int neighbor, weight;
            tie(neighbor, weight) = edge;
            if (visited.find(neighbor) == visited.end() && val + weight < dist[neighbor]) {
                dist[neighbor] = val + weight;
                q.push({dist[neighbor], neighbor});
            }
        }
    }

    return dist;
}
int findCentralNode(int nodes, const vector<int>& tree_from, const vector<int>& tree_to, const vector<int>& tree_weight, int x, int y, int z) {
    unordered_map<int, vector<pair<int, int>>> h;
    int n = nodes;
    for (size_t i = 0; i < tree_from.size(); ++i) {
        h[tree_from[i]].push_back({tree_to[i], tree_weight[i]});
        h[tree_to[i]].push_back({tree_from[i], tree_weight[i]});
    }
    vector<int> dx = solve(x, n, h);
    vector<int> dy = solve(y, n, h);
    vector<int> dz = solve(z, n, h);
    int ans = INT_MAX;
    int mns = -1;
    for (int i = 1; i <= n; ++i) {
        int val = dx[i] + dy[i] + dz[i];
        if (val < ans) {
            ans = val;
            mns = i;
        }
    }
    return mns;
}