Trước tiên ta chặt nhị phân đáp án. Với mỗi đáp án ~x~, ta cần giải bài toán cặp ghép:

• Xem các đỉnh thể hiện vị trí của người dân là phía bên trái, còn các đỉnh thể hiện các điểm sơ tán ở phía bên phải

• Biết người dân ~i~ chỉ đi đến các điểm sơ tán ~j~ mà ~\text{dist(i,j)} \le x~, kiểm tra xem có tồn tại cặp ghép đầy đủ thoả mãn điều kiện về sức chứa cho các điểm sơ tán hay không.

Theo định lí Hall, một cặp ghép đầy đủ tồn tại khi và chỉ khi với mỗi tập con gồm ~k~ đỉnh của phía bên trái, tồn tại một tập con gồm ~\ge k~ đỉnh ở phía bên phải mà mỗi đỉnh trong tập con ở phía bên phải kề với ít nhất một đỉnh nằm trong tập con ở phía bên trái. Áp dụng cho bài toán này: với mỗi tập con ~k~ người dân, cần kiểm tra xem có tồn tại một tập con các điểm sơ tán thoả mãn đồng thời:

• Tổng sức chứa của các điểm ~\ge k~

• Với mỗi người dân ~i~ trong tập, tồn tại một điểm sơ tán tương ứng ~j~ mà ~\text{dist(i,j)} \le x~

(khi tách các điểm sơ tán có sức chứa ~k_i~ thành ~k_i~ điểm sơ tán con, thì bài toán quay về đúng như định lí Hall phát biểu)

Vì số người dân quá nhiều, nên ta không thể duyệt hết ~2^k~ tập các người dân để kiểm tra. Ta sẽ làm ngược lại: với mỗi tập con ~S~ các điểm sơ tán, ta xem tập con của các người dân chỉ có thể đi đến các điểm sơ tán thuộc ~S~ có kích thước tối đa là bao nhiêu. Bởi vì nếu ta có một tập con các người dân và một tập con các điểm sơ tán thoả mãn, thì khi ta thu nhỏ tập người dân lại, điều kiện vẫn được thoả mãn. Nên ta chỉ cần so sánh tổng sức chứa của một subset các điểm sơ tán với tập người dân có lực lượng lớn nhất có thể, nếu không đủ thì không có cách ghép thoả mãn.

Như vậy ta có thuật toán để kiểm tra với mỗi khoảng cách xa nhất ~x~:

• Với mỗi người dân ~i~, tính ~S[i]~ là tập các điểm sơ tán mà ~i~ có thể đi đến được

• Gọi ~dp[mask]~ là số lượng ~S[i]=mask~ hoặc tập con của ~mask~. Dễ dàng tính ~dp[mask]~ bằng DP SOS.

• Với mỗi cách chọn ~mask~, tính tổng sức chứa của các điểm sơ tán thuộc ~mask~, và so sánh với ~dp[mask]~. Nếu nhỏ hơn thì trả về false

Độ phức tạp: ~O(nk \log{n} + (n+2^k)k \log{(10^9)})~

#include <bits/stdc++.h>
#define int long long
#define BIT(i, x) (((x) >> (i)) & 1)
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e6 + 5;
const int B = 25;
const ll Inf = 1e14;
int n, m, k;
int x[B];
int dp[N];
ll d[B][N];
vector<pair<int, ll>> nadj[N];
int bonker[B];

void Read()
{
    cin >> n >> k;
    m = n - 1;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        nadj[u].push_back({v, w});
        nadj[v].push_back({u, w});
    }
    for (int i = 1; i <= k; ++i)
        cin >> bonker[i] >> x[i];
}

bool Check(int v)
{
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; ++i)
    {
        int cur = 0;
        for (int j = 1; j <= k; ++j)
            if (d[j][i] <= v)
                cur |= 1 << (j - 1);
        ++dp[cur];
    }
    //cout << dp[1] << "\n";
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j < (1 << k); ++j)
            if (BIT(i - 1, j))
                dp[j] += dp[j ^ (1 << (i - 1))];
    for (int j = 0; j < (1 << k); ++j)
    {
        ll cap = 0;
        for (int i = 0; i < k; ++i)
            if (BIT(i, j))
                cap += x[i + 1];
        //cout << j << ": " << cap << " " << dp[j] << "\n";
        if (cap < dp[j])
            return false;
    }
    return true;
}

bool Relax(int son, int par, ll w, ll d[N])
{
    if (d[son] > d[par] + w)
    {
        d[son] = d[par] + w;
        return true;
    }
    return false;
}

void Dijkstra(int x, ll d[N])
{
    fill_n(d, N, Inf);
    d[x] = 0;
    struct Tque
    {
        int v;
        ll w;
        Tque() {}
        Tque(int v, ll w)
        {
            this->v = v;
            this->w = w;
        }
        bool operator<(const Tque &a) const
        {
            return w > a.w;
        }
        bool Valid(ll d[])
        {
            return d[v] == w;
        }
    };
    priority_queue<Tque> s;
    s.push(Tque(x, 0));
    while (s.size())
    {
        Tque c = s.top();
        s.pop();
        if (!c.Valid(d))
            continue;
        for (auto i : nadj[c.v])
            if (Relax(i.first, c.v, i.second, d))
                s.push(Tque(i.first, d[i.first]));
    }
}

void Solve()
{

    for (int i = 1; i <= k; ++i)
        Dijkstra(bonker[i], d[i]);
    ll l = 0, m, h = Inf;
    while (l <= h)
    {
        m = (l + h) / 2;
        if (Check(m))
            h = m - 1;
        else
            l = m + 1;
    }
    cout << l;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}