---
# System prepended metadata

title: COCI 2019/2020 - Contest 5 - Putovanje

---

Source: https://oj.vnoi.info/problem/coci1920_r5_putovanje
```cpp=
// Goten2308
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
//#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a <= 0) a += MOD; }

const int maxN = (int)2e5 + 7, maxLog = 31 - __builtin_clz(maxN) + 1;
int n;
struct Edge {
    int to, c1, c2;
    Edge (int _to, int _c1, int _c2) {
        to = _to;
        c1 = _c1;
        c2 = _c2;
    }
};
vector <Edge> G[maxN];

namespace subtask2 {
    struct DSU {
        vector <int> lab;
        DSU(int sz) {
            lab.resize(sz + 1, -1);
        }

        int findRoot(int u) {
            if(lab[u] < 0) return u;
            return lab[u] = findRoot(lab[u]);
        }

        bool join(int u, int v) {
            u = findRoot(u);
            v = findRoot(v);
            if(u == v) return 0;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            return 1;
        }

        bool sameSet(int u, int v) {
            return findRoot(u) == findRoot(v);
        }
    };

    struct Adj {
        int f, t, c1, c2;
        Adj() {}
        Adj(int _f, int _t, int _c1, int _c2) {
            f = _f;
            t = _t;
            c1 = _c1;
            c2 = _c2;
        }
    };
    vector <Adj> adj;
    void solve() {
        for(int i = 1; i <= n; i++) {
            for(auto j : G[i]) if(i < j.to) adj.pb(Adj(i, j.to, j.c1, j.c2));
        }
        ll ans = 0;
        for(int i = 0; i < adj.size(); i++) {
            DSU dsu(n);
            int cnt = 0;
            for(int j = 0; j < adj.size(); j++) {
                if(j == i) continue;
                dsu.join(adj[j].f, adj[j].t);
            }
            for(int i = 1; i < n; i++) {
                if(!dsu.sameSet(i, i + 1)) cnt++;
            }
            ans += min(1ll * cnt * adj[i].c1, 1ll * adj[i].c2);
        }
        cout << ans << endl;
    }
}

namespace subtask3 {
    const int maxLog = 22;
    int par[maxN][maxLog + 7], h[maxN], f[maxN];

    void DFS(int u, int p) {
        for(auto nxt : G[u]) {
            int v = nxt.to;
            if(v == p) continue;
            par[v][0] = u;
            h[v] = h[u] + 1;
            for(int i = 1; i <= maxLog; i++) par[v][i] = par[par[v][i - 1]][i - 1];
            DFS(v, u);
        }
    }

    int LCA(int u, int v) {
        if(h[u] != h[v]) {
            if(h[u] < h[v]) swap(u, v);
            int diff = h[u] - h[v];
            for(int i = 0; (1 << i) <= diff; i++) {
                if(BIT(diff, i)) u = par[u][i];
            }
        }
        if(u == v) return u;
        int lg = 31 - __builtin_clz(h[u]);
        for(int i = lg; i >= 0; i--) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
        return par[u][0];
    }

    void DFS2(int u, int p) {
        for(auto nxt : G[u]) {
            int v = nxt.to;
            if(v == p) continue;
            DFS2(v, u);
            f[u] += f[v];
        }
    }

    void solve() {
        DFS(1, 0);
        for(int i = 1; i < n; i++) {
            int p = LCA(i, i + 1);
            f[i]++;
            f[i + 1]++;
            f[p] -= 2;
        }
        DFS2(1, 0);
        ll ans = 0;
        for(int i = 1; i <= n; i++) {
            for(auto nxt : G[i]) {
                int j = nxt.to;
                if(h[i] > h[j]) {
                    ans += min(1ll * f[i] * nxt.c1, 1ll * nxt.c2);
                }
            }
        }
        cout << ans << endl;
    }
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        G[u].pb(Edge(v, c1, c2));
        G[v].pb(Edge(u, c1, c2));
    }
    //if(n <= (int)2e3)subtask2::solve();
    //else subtask3::solve();
    subtask3::solve();
}

signed main(){
    #define task "friend"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        //freopen("task.out", "w", stdout);
    }
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int nTest = 1;
    #ifdef MULTI_TEST
    cin >> nTest;
    #endif
    while(nTest--) {
        solve();
    }
    return 0;
}

```