1471
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
#pragma comment(linker, "/STACK:16777216") for C/C++
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define mp                make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"
 
vector< vector< ii > > tree;
vector< bool > s;
vector< int > c;
int treeRoot = -1;
 
void buildTree(int size)
{
    tree.resize(size);
    s.resize(size);
    c.resize(size);
}
 
void addEdge(int u, int v, int w)
{
    /* two edges */
    tree[u].pb(mp(v,w));
    tree[v].pb(mp(u,w));
}
 
void assignRoot(int u)
{
    treeRoot = u;
}
 
void dfs(int u, int w)
{
    if(!s[u])
    {
        /* not visited */
        s[u] = true;
        c[u] = w;
        for(vector< ii >:: iterator it = tree[u].begin(); it != tree[u].end(); it ++)
        {
            if(!s[(*it).first])
            {
                dfs((*it).first, w + (*it).second);
            }
        }
    }
    s[u] = false;
}
 
/* for LCA */
vi E;
vi L;
vi R;
 
void init_lca(int n)
{
    R.resize(n);
    E.reserve(2*n);
    L.reserve(2*n);
}
 
void dfs_lca(int u, int l)
{
    if(!s[u])
    {
        E.pb(u);
        L.pb(l);
        R[u] = sz(E)-1;
 
        /* not visited */
        s[u] = true;
        for(vector< ii >:: iterator it = tree[u].begin(); it != tree[u].end(); it ++)
        {
            if(!s[(*it).first])
            {
                dfs_lca((*it).first, l + 1);
                E.pb(u);
                L.pb(l);
            }
        }
    }
    s[u] = false;
}
 
/* for RMQ */
 
int M[100010][20];
 
inline int nlz(unsigned x) {
    int n;
 
    if (x == 0) return(32);
    n = 0;
    if (x <= 0x0000FFFF) {n = n +16; x = x <<16;}
    if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;}
    if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;}
    if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;}
    if (x <= 0x7FFFFFFF) {n = n + 1;}
    return n;
}
 
void init_rmq(vi &A)
{
 
}
 
void rmq_prep(vi &A)
{
    int i, j;
 
    for (i = 0; i < sz(A); i++)
        M[i][0] = i;
 
    for (j = 1; 1 << j <= sz(A); j++)
    {
        for (i = 0; i + (1 << j) - 1 < sz(A); i++)
        {
            if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
                M[i][j] = M[i][j - 1];
            else
                M[i][j] = M[i + (1 << (j - 1))][j - 1];
        }
    }
} 
 
int rmq(vi &A, int i, int j)
{
    int k = 31 - nlz(j-i+1);
 
    if(A[ M[i][k] ] <= A[ M[j - (1<<k) + 1][k] ])
        return M[i][k];
    else
        return M[j - (1<<k) + 1][k];
}
 
int main(void)
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    //freopen(INPUT_FILE, "r", stdin);
    //freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int n;
    int m;
 
    cin >> n;
 
    buildTree(n);
 
    FOR(i,n-1)
    {
        int u,v,w;
        cin >> u >> v >> w;
        addEdge(u,v,w);
    }
 
    assignRoot(0);
    dfs(treeRoot, 0);
 
    init_lca(n);
    dfs_lca(treeRoot, 0);
 
    rmq_prep(L);
 
    cin >> m;
    FOR(i,m)
    {
        int u,v,p;
        cin >> u >> v;
        p = E[ rmq(L, min(R[u], R[v]), max(R[u], R[v])) ];
        cout << c[u] + c[v] - 2*c[p] << endl;
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.