Trip Discount

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

#define NMAX 10010
#define LOGMAX 16
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair< ll, ll > pll;

ll n;
vector< pll > grafo[NMAX];

ll pai[NMAX];
ll wpai[NMAX];
ll level[NMAX];

ll vet[NMAX];

ll anc[NMAX][LOGMAX + 1LL];

ll in[NMAX];
ll out[NMAX];
ll who[NMAX];
vector< ll > order;

ll accu[NMAX];

ll bestDist;
pll best;

pll invalid = {-1LL, -1LL};

bool passed[NMAX];

pll st[4LL * NMAX];
ll la[4LL * NMAX];

void DFS(ll u, ll d)
{

    anc[u][0] = pai[u];
    for(ll i = 1;i <= LOGMAX;i++)
        anc[u][i] = anc[ anc[u][i - 1] ][i - 1];

    in[u] = order.size();

    vet[in[u]] = d;
    who[in[u]] = u;

    order.pb(u);

    ll v, w;

    for(auto viz : grafo[u])
    {

        w = viz.fi;
        v = viz.se;

        if(pai[v] != 0LL) continue;

        pai[v] = u;
        wpai[v] = w;
        level[v] = level[u] + 1;

        DFS(v, d + w);

    }

    out[u] = order.size() - 1LL;

    return;

}

void DFS(ll u)
{

    for(ll i = 1;i <= n;i++) pai[i] = 0LL;

    order.clear();

    pai[u] = u;
    wpai[u] = 0;
    level[u] = 0LL;
    DFS(u, 0LL);

    return;

}

ll LCA(ll u, ll v)
{

    if(level[u] < level[v]) swap(u, v);

    ll i;

    for(i = LOGMAX;i >= 0;i--)
    {

        if(level[u] - (1LL << i) >= level[v]) u = anc[u][i];

    }

    if(u != v)
    {

        for(i = LOGMAX;i >= 0;i--)
        {

            if(anc[u][i] != anc[v][i])
            {

                u = anc[u][i];
                v = anc[v][i];

            }

        }

        u = anc[u][0];
        v = anc[v][0];

    }

    return u;

}

ll changeEdges(ll u)
{

    ll v, w, x;

    x = accu[u];

    for(auto viz : grafo[u])
    {

        w = viz.fi;
        v = viz.se;

        if(v == pai[u]) continue;

        x += changeEdges(v);

    }

    wpai[u] = x * wpai[u];

    return x;

}

pll findDiameter(ll u)
{

    ll v, w;

    pll ma, ma2, x;

    ma = invalid;
    ma2 = invalid;

    for(auto viz : grafo[u])
    {

        w = viz.fi;
        v = viz.se;

        if(v == pai[u]) continue;

        x = findDiameter(v);
        x.fi += w;

        ma2 = max(ma2, x);

        if(ma < ma2) swap(ma, ma2);

    }

    if(ma == invalid) ma = {0LL, u};
    if(ma2 == invalid) ma2 = {0LL, u};

    if(bestDist < ma.fi + ma2.fi)
    {

        bestDist = ma.fi + ma2.fi;
        best = {ma.se, ma2.se};

    }

    return ma;

}

void Lazy(ll idx, ll l, ll r)
{

    if(la[idx] == 0LL) return;

    st[idx].fi += la[idx];

    ll nxt = (idx << 1LL);

    if(l != r)
    {

        la[nxt] += la[idx];
        la[nxt + 1LL] += la[idx];

    }

    la[idx] = 0;

    return;

}

void Build(ll idx, ll l, ll r)
{

    if(l == r)
    {

        st[idx] = {vet[l], who[l]};
        la[idx] = 0LL;

        return;

    }

    ll nxt = (idx << 1LL), mid = ((l + r) >> 1LL);

    Build(nxt, l, mid);
    Build(nxt + 1LL, mid + 1LL, r);

    st[idx] = max(st[nxt], st[nxt + 1LL]);

    return;

}

void Update(ll idx, ll l, ll r, ll a, ll b, ll val)
{

    Lazy(idx, l, r);

    if(a <= l && r <= b)
    {

        la[idx] += val;

        Lazy(idx, l, r);

        return;

    }

    if(r < a || b < l) return;

    ll nxt = (idx << 1LL), mid = ((l + r) >> 1LL);

    Update(nxt, l, mid, a, b, val);
    Update(nxt + 1LL, mid + 1LL, r, a, b, val);

    st[idx] = max(st[nxt], st[nxt + 1LL]);

    return;

}

ll Erase(ll u)
{

    ll v, x, sum;

    pll *edge;

    sum = 0LL;

    while(passed[u] == false)
    {

        sum += wpai[u];

        Update(1LL, 0LL, n - 1LL, in[u], out[u], -wpai[u]);

        passed[u] = true;

        u = pai[u];

    }

    return sum;

}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll tt, q, k, u, v, w, resp, i, j;

    cin >> tt;

    while(tt--)
    {

        resp = 0LL;
        bestDist = -1LL;

        cin >> n >> k >> q;

        for(i = 1;i <= n;i++) grafo[i].clear();

        for(i = 1;i <= n;i++) accu[i] = 0LL;

        for(i = 2;i <= n;i++)
        {

            cin >> u >> v >> w;

            grafo[u].pb({w, v});
            grafo[v].pb({w, u});

        }

        DFS(1LL);

        while(q--)
        {

            cin >> u >> v;

            accu[u] += 1LL;
            accu[v] += 1LL;
            accu[LCA(u, v)] -= 2LL;

        }

        changeEdges(1LL);

        for(i = 1;i <= n;i++) resp += wpai[i];

        // Remontando grafo

        for(i = 1;i <= n;i++) grafo[i].clear();

        for(i = 2;i <= n;i++)
        {

            u = i;
            v = pai[i];
            w = wpai[i];

            grafo[u].pb({w, v});
            grafo[v].pb({w, u});

        }

        findDiameter(1LL);

        k--; // choose best.fi
        DFS(best.fi);
        passed[best.fi] = true;

        Build(1LL, 0LL, n - 1LL);

        while(k--) resp -= Erase(st[1LL].se);

        cout << resp << "\n";

    }

    return 0;

}