c.cpp

#include<bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define ll long long

using namespace std;
const int MAXN = 1e6 + 10;
const ll INF = 1e18 + 7;
bool was[MAXN];
vector <pair <int, int> > g[MAXN];
int up[MAXN][23];
ll d[MAXN];
int tin[MAXN], tout[MAXN], l, n, s, t;
bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int timer = 0;
void dfs(int x, ll dis = 0, int p = 0){
    was[x] = 1;
    tin[x] = ++timer;
    up[x][0] = p;
    d[x] = dis;
    for (int i = 1; i <= l; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }

    for (int i = 0; i < g[x].size(); i++){
        int to = g[x][i].f;
        int len = g[x][i].s;
        if (!was[to]){
            dfs(to, dis + len, x);
        }
    }
    tout[x] = ++timer;
}

int lca(int a, int b){
    if (upper(a, b))
        return a;
    if (upper(b, a))
        return b;

    for (int i = l; i >= 0; i--){
        if (!upper(up[a][i], b))
            a = up[a][i];
    }

    return up[a][0];
}

ll dist(int x, int y){
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

bool check(int u, int v, int a1, int b1){
    int lcauv = lca(u, v);

    if (upper(a1, lcauv) && upper(b1, lcauv)){
        return 1;
    }
    if (upper(a1, u) && upper(b1, u)){
        return false;
    }
    if (upper(a1, v) && upper(b1, v)){
        return false;
    }
    return true;
}

void solve(){
    tout[0] = 1e9 + 7;
    l = 0;
    while ((1 << l) < MAXN){
        l++;
    }

    cin >> n >> s >> t;

    for (int i = 1; i < n; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        g[x].pb({y, cost});
        g[y].pb({x, cost});
    }
    dfs(1);
    int q;
    cin >> q;
    while (q--){
        int a1, b1, a2, b2, cost2;
        cin >> a1 >> b1 >> a2 >> b2 >> cost2;
        ll new_dist = INF;
        if (check(s, t, a1, b1)){
            new_dist = min(new_dist, dist(s, t));
        }
        if (check(s, a2, a1, b1) && check(b2, t, a1, b1)){
            new_dist = min(new_dist, dist(s, a2) + dist(b2, t) + cost2);
        }
        if (check(s, b2, a1, b1) && check(a2, t, a1, b1)){
            new_dist = min(new_dist, dist(s, b2) + dist(a2, t) + cost2);
        }

        if (new_dist == INF){
            cout << -1 << '\n';
        }
        else {
            cout << new_dist << '\n';
        }
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int ttt = 1;
    //cin >> ttt;

    while (ttt--){
        solve();
    }
    return 0;
}