LCA , sparsetable

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const ll INF = 100000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

int N, M;

int depth[100002];
int par[100002][22];
int dist[100002];
vector<pii> graph[100002];
int maxhi;
int visited[100002];

void dfs(int curr,int dep, int dis) 
{
    dist[curr] = dis;
    depth[curr] = dep;
    visited[curr] = 1;
    for (auto k : graph[curr]) 
    {
        if (!visited[k.first]) 
        {
            par[k.first][0] = curr;
            dfs(k.first,dep + 1,dis + k.second );
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    memset(depth, 0, sizeof(depth));

    int a, b, c;

    cin >> N;

    for (int i = 0; i < N - 1; i++)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b, c });
        graph[b].push_back({ a, c });
    }

    //초기화
    depth[1] = 1;
    visited[1] = 1;
    dist[1] = 0;

    //트리 만들기
    dfs(1, 0, 0);

    //par 배열 채우기
    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= N; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];

    cin >> M;

    while (M--)
    {
        cin >> a >> b;

        int pa = a;
        int pb = b;

        if (depth[a] < depth[b]) 
            swap(a, b);

        int diff = depth[a] - depth[b];

        for (int j = 0; diff; j++) 
        {
            if (diff % 2) 
                a = par[a][j];
            diff /= 2;
        }

        if (a != b)
        {
            for (int i = 20; i >= 0; i--)
            {
                if (par[a][i] != -1 && par[a][i] != par[b][i])
                {
                    a = par[a][i];
                    b = par[b][i];
                }
            }
            a = par[a][0];
        }

        cout << dist[pa] + dist[pb] - 2 * dist[a] << "\n";
    }

	return 0;
}