#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int mod = 1e9 + 7 ;
vector< set< int > > v; //The actual graph
vector< int > par, level, sub; //par[i]==parent of node i in centroid tree, level[i] = level of node i in centroid tree, sub[i] = number of nodes in subarray of i
vector< vector< int > > ans; //ans[i][j]==max wt edge in path from i to j
map< pair< int , int > , int > m; //m[{u, v}] = wieght of edge {u, v}
map< int , pair< int , int > > rank; //index of {u, v} edge
int root; //First centroid of original tree.
void dfsinit( int u, int p)
{
sub[ u] = 1 ;
for ( int i: v[ u] )
{
if ( i== p) continue ;
dfsinit( i, u) ;
sub[ u] + = sub[ i] ;
}
}
int findcentroid( int u, int p, int root)
{
int ret = u;
for ( int i: v[ u] )
{
if ( i== p) continue ;
if ( sub[ i] >= sub[ root] / 2 .)
ret = findcentroid( i, u, root) ;
}
return ret;
}
void dfs( int u, int p, int lvl, int maxans)
{
ans[ lvl] [ u] = max( ans[ lvl] [ u] , maxans) ;
for ( int i: v[ u] )
{
if ( i== p) continue ;
dfs( i, u, lvl, max( maxans, m[ { i, u} ] ) ) ;
}
}
void decompose( int u, int p, int lvl)
{
dfsinit( u, - 1 ) ;
int centroid = findcentroid( u, - 1 , u) ;
if ( u== 0 ) root = centroid;
par[ centroid] = p;
level[ centroid] = lvl;
dfs( centroid, - 1 , lvl, 0 ) ;
for ( int i: v[ centroid] )
{
v[ i] .erase ( centroid) ;
decompose( i, centroid, lvl+ 1 ) ;
v[ i] .insert ( centroid) ;
}
}
int query( int a, int b)
{
int ta = a, tb = b, lcs;
if ( level[ ta] > level[ tb] )
swap( ta, tb) ;
while ( level[ ta] < level[ tb] )
tb = par[ tb] ;
while ( ta! = tb)
ta = par[ ta] , tb = par[ tb] ;
lcs = ta;
return max( ans[ level[ lcs] ] [ a] , ans[ level[ lcs] ] [ b] ) ;
}
main( )
{
ios_base:: sync_with_stdio ( 0 ) ;
cin .tie ( 0 ) ;
cout .tie ( 0 ) ;
int n;
cin >> n;
v.resize ( n) ;
par.resize ( n) ;
sub.resize ( n) ;
level.resize ( n) ;
ans.resize ( 20 , vector< int > ( n) ) ;
for ( int i = 0 ; i< n- 1 ; i++ )
{
int x, y, c;
cin >> x>> y>> c;
m[ { x- 1 , y- 1 } ] = m[ { y- 1 , x- 1 } ] = c;
v[ x- 1 ] .insert ( y- 1 ) ;
v[ y- 1 ] .insert ( x- 1 ) ;
}
decompose( 0 , - 1 , 1 ) ;
//test the centroid tree formed, printing i and parent of i inc entroid tree
for ( int i = 0 ; i< n; i++ )
cout << i<< " " << par[ i] << endl;
int q = 0 ; //Take number of queries
cin >> q;
while ( q-- )
{
int a, b;
cin >> a>> b;
cout << query( a- 1 , b- 1 ) << endl;
}
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZyBpbnQKCmNvbnN0IGludCBtb2QgPSAxZTkrNzsKdmVjdG9yPCBzZXQ8aW50PiA+IHY7Ly9UaGUgYWN0dWFsIGdyYXBoCnZlY3RvcjxpbnQ+IHBhciwgbGV2ZWwsIHN1YjsvL3BhcltpXT09cGFyZW50IG9mIG5vZGUgaSBpbiBjZW50cm9pZCB0cmVlLCBsZXZlbFtpXSA9IGxldmVsIG9mIG5vZGUgaSBpbiBjZW50cm9pZCB0cmVlLCBzdWJbaV0gPSBudW1iZXIgb2Ygbm9kZXMgaW4gc3ViYXJyYXkgb2YgaQp2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gYW5zOy8vYW5zW2ldW2pdPT1tYXggd3QgZWRnZSBpbiBwYXRoIGZyb20gaSB0byBqCm1hcDwgcGFpcjxpbnQsIGludD4sIGludCA+IG07Ly9tW3t1LCB2fV0gPSB3aWVnaHQgb2YgZWRnZSB7dSwgdn0KbWFwPGludCwgcGFpcjxpbnQsIGludD4gPiByYW5rOy8vaW5kZXggb2Yge3UsIHZ9IGVkZ2UKaW50IHJvb3Q7Ly9GaXJzdCBjZW50cm9pZCBvZiBvcmlnaW5hbCB0cmVlLgp2b2lkIGRmc2luaXQoaW50IHUsIGludCBwKQp7CiAgICBzdWJbdV0gPSAxOwogICAgZm9yKGludCBpOiB2W3VdKQogICAgewogICAgICAgIGlmKGk9PXApY29udGludWU7CiAgICAgICAgZGZzaW5pdChpLCB1KTsKICAgICAgICBzdWJbdV0rPXN1YltpXTsKICAgIH0KfQppbnQgZmluZGNlbnRyb2lkKGludCB1LCBpbnQgcCwgaW50IHJvb3QpCnsKICAgIGludCByZXQgPSB1OwogICAgZm9yKGludCBpOiB2W3VdKQogICAgewogICAgICAgIGlmKGk9PXApY29udGludWU7CiAgICAgICAgaWYoc3ViW2ldPj1zdWJbcm9vdF0vMi4pCiAgICAgICAgICAgIHJldCA9IGZpbmRjZW50cm9pZChpLCB1LCByb290KTsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0Kdm9pZCBkZnMoaW50IHUsIGludCBwLCBpbnQgbHZsLCBpbnQgbWF4YW5zKQp7CgkKICAgIGFuc1tsdmxdW3VdID0gbWF4KGFuc1tsdmxdW3VdLCBtYXhhbnMpOwogICAgZm9yKGludCBpOiB2W3VdKQogICAgewogICAgICAgIGlmKGk9PXApY29udGludWU7CiAgICAgICAgZGZzKGksIHUsIGx2bCwgbWF4KG1heGFucywgbVt7aSwgdX1dKSk7CiAgICB9Cn0Kdm9pZCBkZWNvbXBvc2UoaW50IHUsIGludCBwLCBpbnQgbHZsKQp7CglkZnNpbml0KHUsIC0xKTsKCWludCBjZW50cm9pZCA9IGZpbmRjZW50cm9pZCh1LCAtMSwgdSk7CglpZih1PT0wKXJvb3QgPSBjZW50cm9pZDsKCXBhcltjZW50cm9pZF0gPSBwOwoJbGV2ZWxbY2VudHJvaWRdID0gbHZsOwoJZGZzKGNlbnRyb2lkLCAtMSwgbHZsLCAwKTsKCWZvcihpbnQgaTogdltjZW50cm9pZF0pCgl7CgkJdltpXS5lcmFzZShjZW50cm9pZCk7CgkJZGVjb21wb3NlKGksIGNlbnRyb2lkLCBsdmwrMSk7CgkJdltpXS5pbnNlcnQoY2VudHJvaWQpOwoJfQp9CmludCBxdWVyeShpbnQgYSwgaW50IGIpCnsKCWludCB0YSA9IGEsIHRiID0gYiwgbGNzOwoJaWYobGV2ZWxbdGFdPmxldmVsW3RiXSkKCQlzd2FwKHRhLCB0Yik7Cgl3aGlsZShsZXZlbFt0YV08bGV2ZWxbdGJdKQoJCXRiID0gcGFyW3RiXTsKCXdoaWxlKHRhIT10YikKCQl0YSA9IHBhclt0YV0sIHRiID0gcGFyW3RiXTsKCWxjcyA9IHRhOwoJcmV0dXJuIG1heChhbnNbbGV2ZWxbbGNzXV1bYV0sIGFuc1tsZXZlbFtsY3NdXVtiXSk7Cn0KCm1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKICAgIGNvdXQudGllKDApOwogICAgCiAgICBpbnQgbjsKICAgIGNpbj4+bjsKICAgIHYucmVzaXplKG4pOwogICAgcGFyLnJlc2l6ZShuKTsKICAgIHN1Yi5yZXNpemUobik7CiAgICBsZXZlbC5yZXNpemUobik7CiAgICBhbnMucmVzaXplKDIwLCB2ZWN0b3I8aW50PihuKSk7CiAgICBmb3IoaW50IGkgPSAwO2k8bi0xO2krKykKICAgIHsKICAgIAlpbnQgeCwgeSwgYzsKICAgIAljaW4+Png+Pnk+PmM7CiAgICAJbVt7eC0xLCB5LTF9XSA9IG1be3ktMSwgeC0xfV0gPSBjOwogICAgCXZbeC0xXS5pbnNlcnQoeS0xKTsKICAgIAl2W3ktMV0uaW5zZXJ0KHgtMSk7CiAgICB9CiAgICBkZWNvbXBvc2UoMCwgLTEsIDEpOwogICAgLy90ZXN0IHRoZSBjZW50cm9pZCB0cmVlIGZvcm1lZCwgcHJpbnRpbmcgaSBhbmQgcGFyZW50IG9mIGkgaW5jIGVudHJvaWQgdHJlZQogICAgZm9yKGludCBpID0gMDtpPG47aSsrKQoJY291dDw8aTw8IiAiPDxwYXJbaV08PGVuZGw7CiAgICBpbnQgcSA9IDA7Ly9UYWtlIG51bWJlciBvZiBxdWVyaWVzCiAgICBjaW4+PnE7CiAgICB3aGlsZShxLS0pCiAgICB7CiAgICAJaW50IGEsIGI7CiAgICAJY2luPj5hPj5iOwogICAgCWNvdXQ8PHF1ZXJ5KGEtMSwgYi0xKTw8ZW5kbDsKICAgIH0KICAgIAoKCiAgICByZXR1cm4gMDsKfSA=