1271 Timus

/*
    Author: ChimitovZ
*/
#include <bits/stdc++.h>

#pragma comment(linker, "/STACK:16777216")

using namespace std;

int N;
vector<int> Costs, Tour;
vector< vector<int> > G;
vector< vector<short> > W;
vector<char> used;

inline void calcDepthsAndCosts();
inline void calcTour(int v);
inline void printAns(int a, int b);

int main()
{
    cin >> N;
    Costs.resize(N);
    used.resize(N, 'f');
    G.resize(N);
    W.resize(N, vector<short>(N));
    for(int i = 1, u, v, w; i < N; ++i){
        cin >> u >> v >> w;
        G[u].push_back(v);
        G[v].push_back(u);
        W[u][v] = w;
        W[v][u] = w;
    }
    calcDepthsAndCosts();
    /* -=Вывод всех глубин и стоимостей=-
    for(int i = 0; i < N; ++i){
        cout << "Вершина №" << i << ", Глубина = " << Depths[i] << ", Стоимость пути = " << Costs[i] << endl;
    }
    */
    calcTour(0);
    for(int i = 0; i < N; ++i){
        G[i].clear();
    }
    /* -=Вывод пути Эйлера=-
    cout << "Tour:\n";
    for(int i = 0; i < Tour.size(); ++i){
        cout << Tour[i] << " ";
    }
    cout << "\n";
    //*/
    int M;
    cin >> M;
    for(int i = 0, a, b; i < M; ++i){
        cin >> a >> b;
        printAns(a, b);
        cout << "\n";
    }
    return 0;
}

inline void calcDepthsAndCosts()
{
    queue<int> Q;
    vector<char> usedTwo;
    usedTwo.resize(N, 'f');
    Q.push(0);
    Costs[0] = 0;
    while(!Q.empty()){
        int cur = Q.front();
        usedTwo[cur] = 't';
        Q.pop();
        for(int i = 0; i < G[cur].size(); ++i){
            int to = G[cur][i];
            if(usedTwo[to] == 'f'){
                Q.push(to);
                Costs[to] = Costs[cur] + W[cur][to];
            }
        }
    }
}

inline void calcTour(int v)
{
    used[v] = 't';
    Tour.push_back(v);
    for(int i = 0; i < G[v].size(); ++i){
        int to = G[v][i];
        if(used[to] == 'f'){
            calcTour(to);
        }
        if(G[v].size() > 1){
            Tour.push_back(v);
        }
    }
}

inline void printAns(int a, int b)
{
    if(a == b){
        cout << 0;
        return;
    }
    int l, r;
    bool flagA = 0, flagB = 0;
    for(int i = 0; i < Tour.size(); ++i){
        if(flagA == 0 && Tour[i] == a){
            l = i;
            flagA = 1;
        }
        if(flagB == 0 && Tour[i] == b){
            r = i;
            flagB = 1;
        }
        if(flagA && flagB){
            break;
        }
    }
    if(l > r){
        swap(l, r);
    }
    int mnNumber = Tour[l];
    for(int i = l; i <= r; ++i){
        if(Costs[Tour[i]] < Costs[mnNumber]){
            mnNumber = Tour[i];
        }
    }
    cout << Costs[a] + Costs[b] - 2 * Costs[mnNumber];
}