## Editorial for Lubenica

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 100100
#define oo 1000000000
using namespace std;

int n,b[maxn][3],p[maxn],a[maxn*2],c[maxn*2],d[maxn],e[maxn][18],f[maxn][18],g[maxn][18],h[maxn],u,v,hh;

void visit(int x,int y,int v,int u)
{
d[x]=v; h[x]=u; e[x][0]=y; hh=max(hh,u);
int i;
fr(i,p[x]+1,p[x+1])
if (a[i]!=y) visit(a[i],x,c[i],u+1);
}

void query(int x,int y)
{
int lg,t,i;
v=oo,u=-oo;
if (h[x]<h[y]) swap(x,y);
for (lg=0;1<<lg<=h[x];lg++); lg--;
frr(i,lg,0)
if (h[x]-(1<<i)>=h[y])
{
u=max(u,f[x][i]);
v=min(v,g[x][i]);
x=e[x][i];
}
if (x==y) return;
frr(i,lg,0)
if (e[x][i] && e[x][i]!=e[y][i])
{
u=max(u,max(f[x][i],f[y][i]));
v=min(v,min(g[x][i],g[y][i]));
x=e[x][i]; y=e[y][i];
}
u=max(u,max(d[x],d[y]));
v=min(v,min(d[x],d[y]));
}

int main()
{
int i,j,q,x,y;
scanf("%d",&n);
fr(i,1,n-1)
{
fr(j,0,2) scanf("%d",&b[i][j]);
p[b[i][0]]++; p[b[i][1]]++;
}
fr(i,2,n+1) p[i]+=p[i-1];
fr(i,1,n-1)
{
a[p[b[i][0]]]=b[i][1];
c[p[b[i][0]]--]=b[i][2];
a[p[b[i][1]]]=b[i][0];
c[p[b[i][1]]--]=b[i][2];
}
//pre-compute
visit(1,0,0,0);
fr(i,2,n) f[i][0]=g[i][0]=d[i];
for (j=1;1<<j<=hh;j++)
fr(i,1,n)
if (e[i][j-1])
{
e[i][j]=e[e[i][j-1]][j-1];
f[i][j]=max(f[i][j-1],f[e[i][j-1]][j-1]);
g[i][j]=min(g[i][j-1],g[e[i][j-1]][j-1]);
}
//query
scanf("%d",&q);
while (q--)
{
scanf("%d%d",&x,&y);
query(x,y);
printf("%d %d\n",v,u);
//system("pause");
}
return 0;
}


#### Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;

#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 1e5 + 2, LOGN = 17 + 2;
int P[N][LOGN], L[N], Wmin[N][LOGN], Wmax[N][LOGN], n;
vector<vector<pair<int, int> > > g;

void dfs(int u) {
TR(g[u], it) {
int v = it->first, w = it->second;
if(v != P[u][0]) {
P[v][0] = u; L[v] = L[u] + 1;
Wmin[v][0] = Wmax[v][0] = w;
dfs(v);
}
}
}

void init() {
memset(P, -1, sizeof P);
dfs(0);
for(int j = 1; 1 << j < n; ++j)
for(int u = 0; u < n; ++u)
if(P[u][j-1] != -1) {
P[u][j] = P[P[u][j-1]][j-1];
Wmin[u][j] = min(Wmin[u][j-1], Wmin[P[u][j-1]][j-1]);
Wmax[u][j] = max(Wmax[u][j-1], Wmax[P[u][j-1]][j-1]);
}
}

void query(int u, int v) {
if(L[u] < L[v]) swap(u, v);
int log = 0; for(; 1 << log <= L[u]; ++log); --log;
int wmin = INT_MAX, wmax = INT_MIN;
for(int i = log; i >= 0; --i)
if(L[u] - (1 << i) >= L[v]) {
wmin = min(wmin, Wmin[u][i]);
wmax = max(wmax, Wmax[u][i]);
u = P[u][i];
}
if(u != v) {
for(int i = log; i >= 0; --i)
if(P[u][i] != P[v][i]) {
wmin = min(wmin, min(Wmin[u][i], Wmin[v][i]));
wmax = max(wmax, max(Wmax[u][i], Wmax[v][i]));
u = P[u][i]; v = P[v][i];
}
wmin = min(wmin, min(Wmin[u][0], Wmin[v][0]));
wmax = max(wmax, max(Wmax[u][0], Wmax[v][0]));
}
printf("%d %d\n", wmin, wmax);
}

void enter() {
scanf("%d", &n); g.resize(n);
for(int i = 1; i < n; ++i) {
int u, v, w; scanf("%d%d%d",&u,&v,&w);
g[--u].push_back(make_pair(--v, w));
g[v].push_back(make_pair(u, w));
}
}

void solve() {
int k; scanf("%d", &k);
while(k--) {
int u, v; scanf("%d%d",&u,&v);
query(--u, --v);
}
}

int main() {
enter();
init();
solve();
return 0;
}


program lubenica;
uses    math;
type    e=record
end;
const   maxn=100009;
fi='';
b,mi,ma:array[0..maxn,0..40] of longint;
check:array[0..maxn] of boolean;
inp:text;
n,m,log,k,tt,res,u,v,r1,r2:longint;

procedure input;
var     //inp:text;
i,x,y,w:longint;

begin
assign(inp,fi);
reset(inp);
for i:=1 to n-1 do
begin
inc(m);
inc(m);
end;
end;

procedure init;
var     l,r,i,u,j:longint;
v:e;
begin
l:=1;r:=1;
q[1]:=1;
d[1]:=0;
check[1]:=true;
while l<=r do
begin
u:=q[l];inc(l);
while i>0 do
begin
if (not check[v.v]) then
begin
check[v.v]:=true;
inc(r);
q[r]:=v.v;
d[v.v]:=d[u]+1;
cha[v.v]:=u;
w[v.v]:=v.w;
end;
end;
end;
log:=trunc(ln(n)/ln(2))+1;
for i:=0 to n do
begin
b[i,0]:=cha[i];
ma[i,0]:=w[i];
mi[i,0]:=w[i];
for j:=1 to log do
b[i,j]:=-1;
end;
for j:=1 to log do
for i:=0 to n do
begin
b[i,j]:=b[b[i,j-1],j-1];
mi[i,j]:=min(mi[i,j-1],mi[b[i,j-1],j-1]);
ma[i,j]:=max(ma[i,j-1],ma[b[i,j-1],j-1]);
end;
end;

function getbit(i,j:longint):longint;
begin
exit(i shr (j-1) and 1);
end;

procedure lca(u,v:longint);
var     t,i:longint;
begin
res:=0;
if d[u]>=d[v] then
begin
if d[u]>d[v] then
begin
t:=d[u]-d[v];
for i:=log downto 1 do
if getbit(t,i)=1 then
begin
r1:=min(r1,mi[u,i-1]);
r2:=max(r2,ma[u,i-1]);
u:=b[u,i-1];
end;
end;
if u=v then exit;
for i:=log downto 0 do
if b[u,i]<>b[v,i] then
begin
r1:=min(r1,min(mi[u,i],mi[v,i]));
r2:=max(r2,max(ma[u,i],ma[v,i]));
u:=b[u,i];
v:=b[v,i];
end;
if b[u,0]=b[v,0] then
begin
r1:=min(r1,min(mi[u,0],mi[v,0]));
r2:=max(r2,max(ma[u,0],ma[v,0]));
end;
end
else lca(v,u);
end;

begin
input;
init;
for tt:=1 to k do
begin
r1:=high(longint);r2:=0;
lca(u,v);
writeln(r1,' ',r2);
end;
end.


#### Code mẫu của RR

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define DEBUG(x) { cerr << #x << " = " << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
using namespace std;

const int MN = 100111;
const int INF = 1e9;

int n;                             // number of vertices
vector<int> cost[MN];

const int MAX_LOG = 18;

int father[MAX_LOG + 1][MN];
int nn[MAX_LOG + 1][MN];
int ln[MAX_LOG + 1][MN];
struct LCA { // Index from 1
int depth[MN];

public:
LCA(int root) {
depth[root] = 1;
father[0][root] = -1;
dfs(root, -1);

FOR(i,1,MAX_LOG) {
FOR(u,1,n) { // Change this if index from 0
int x = father[i-1][u];
if (x < 0) {
father[i][u] = -1;
nn[i][u] = INF;
ln[i][u] = -INF;
}
else {
father[i][u] = father[i-1][x];
nn[i][u] = min(nn[i-1][u], nn[i-1][x]);
ln[i][u] = max(ln[i-1][u], ln[i-1][x]);
}
}
}
}

pair<int,int> get(int u, int v) {
pair<int,int> res = make_pair(INF, -INF);
if (u == v) return res;
if (depth[u] > depth[v]) swap(u, v);

if (depth[u] != depth[v]) {
FORD(i,MAX_LOG,0) {
int x = father[i][v];
if (x < 0) continue;
if (depth[x] >= depth[u]) {
res.first = min(res.first, nn[i][v]);
res.second = max(res.second, ln[i][v]);
v = x;
}
}
}
if (u == v) return res;

FORD(i,MAX_LOG,0) {
if (father[i][u] != father[i][v]) {
res.first = min(res.first, min(nn[i][u], nn[i][v]));
res.second = max(res.second, max(ln[i][u], ln[i][v]));
u = father[i][u];
v = father[i][v];
}
}
res.first = min(res.first, min(nn[0][u], nn[0][v]));
res.second = max(res.second, max(ln[0][u], ln[0][v]));
return res;
}

private:
void dfs(int u, int fu) {
REP(id,a[u].size()) {
int v = a[u][id];
if (v == fu) continue;
int c = cost[u][id];

depth[v] = depth[u] + 1;
father[0][v] = u;
nn[0][v] = c;
ln[0][v] = c;
dfs(v, u);
}
}
};

int main() {
ios :: sync_with_stdio(false);
while (cin >> n) {
FOR(i,1,n) {
a[i].clear();
cost[i].clear();
}

FOR(i,2,n) {
int u, v, c; cin >> u >> v >> c;
a[u].push_back(v);
cost[u].push_back(c);

a[v].push_back(u);
cost[v].push_back(c);
}

LCA lca(1);

int q; cin >> q;
while (q--) {
int u, v; cin >> u >> v;
auto res = lca.get(u, v);

cout << res.first << ' ' << res.second << '\n';
}
}
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
program LUBENICA;
uses math;
const
input  = '';
output = '';
maxn = 100003;
maxv = 1000001;
type
pnode = ^tnode;
tnode = record
val,cost: integer;
end;

plist = ^tlist;
tlist = record
val,nlist: integer;
end;
var
n,k: integer;
fi,fo: text;
a: array[1..maxn] of pnode;
b,c: array[1..4 * maxn] of integer;
list,newlist: array[1..maxn] of plist;
anc,anclist,trace: array[1..maxn] of integer;
t1,t2,pre,rank: array[1..maxn] of integer;
minlist,maxlist: array[1..2 * maxn] of integer;
free,col: array[1..maxn] of boolean;
num,ta,tb,tmin,tmax: integer;

procedure openfile;
begin
assign(fi, input);
reset(fi);

assign(fo, output);
rewrite(fo);
end;

var
p: pnode;
begin
new(p);
p^.val := v;
p^.cost := c;
a[u] := p;
end;

var
p: plist;
begin
new(p);
p^.val := v;
p^.nlist := i;
list[u] := p;
end;

procedure init;
var
i,u,v,c: integer;
begin
for i := 1 to n - 1 do
begin
end;

for i := 1 to k do
begin
t1[i] := u;
t2[i] := v;
end;
end;

procedure makeset(x: integer);
begin
pre[x] := x;
rank[x] := 0;
free[x] := false;
end;

function findset(u: integer): integer;
begin
if u <> pre[u]
then pre[u] := findset(pre[u]);
findset := pre[u];
end;

begin
if rank[u] > rank[v] then pre[v] := u else pre[u] := v;
if rank[u] = rank[v] then inc(rank[v]);
end;

procedure union(u,v: integer);
begin
end;

procedure LCA(u: integer);
var
p: pnode;
q: plist;
v: integer;
begin
makeset(u);
anc[findset(u)] := u;

p := a[u];
while p <> nil do
begin
v := p^.val;
if free[v] then
begin
LCA(v);
union(u,v);
anc[findset(u)] := u;
end;
end;

col[u] := true;
q := list[u];
while q <> nil do
begin
v := q^.val;
if col[v] then anclist[q^.nlist] := anc[findset(v)];
end;
end;

procedure update(i,low,high,x: integer);
var
mid: integer;
begin
if low = high then
begin
if low = num then
begin
b[i] := x;
c[i] := x;
end;
exit;
end;

mid := (low + high) div 2;
if num <= mid then update(2 * i,low,mid,x) else update(2 * i + 1,mid + 1,high,x);

b[i] := min(b[2 * i],b[2 * i + 1]);
c[i] := max(c[2 * i],c[2 * i + 1]);
end;

var
mid: integer;
begin
if (tb < low) or (high < ta) then exit;
if (ta <= low) and (high <= tb) then
begin
if tmin > b[i] then tmin := b[i];
if tmax < c[i] then tmax := c[i];
exit;
end;

mid := (low + high) div 2;
answer(2 * i + 1,mid + 1,high);
end;

procedure calc(u: integer);
var
p: pnode;
q: plist;
v,tlist: integer;
begin
free[u] := false;
inc(num);
trace[u] := num;
p := a[u];

while p <> nil do
begin
v := p^.val;
if free[v] then
begin
update(1,1,n,p^.cost);
calc(v);
dec(num);
end;

end;

q := newlist[u];
tb := trace[u];
dec(tb);
while q <> nil do
begin
v := q^.val;
ta := trace[v];

tmin := maxv;
tmax := -maxv;
tlist := q^.nlist;

if ta <= tb then answer(1,1,n);

minlist[tlist] := tmin;
maxlist[tlist] := tmax;

end;
end;

var
p: plist;
begin
new(p);
p^.val := v;
p^.nlist := i;
newlist[u] := p;
end;

procedure query;
var
i: integer;
begin
fillchar(col, sizeof(col), false);
fillchar(free, sizeof(free), true);
LCA(1);

for i := 1 to k do
begin
end;

for i := 1 to 4 * maxn do
begin
b[i] := maxv;
c[i] := -maxv;
end;

num := 0;
fillchar(free, sizeof(free), true);
calc(1);
end;

procedure printresult;
var
i: integer;
begin
for i := 1 to k do
begin
write(fo, min(minlist[2 * i],minlist[2 * i + 1]), ' ');
writeln(fo, max(maxlist[2 * i],maxlist[2 * i + 1]));
end;
end;

procedure closefile;
begin
close(fo);
close(fi);
end;

begin
openfile;
init;
query;
printresult;
closefile;
end.


#### Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<queue>
#define MAX   100100
#define f   first
#define s   second
using namespace std;
typedef pair<int,int> ii;
struct row {
int p,mx,mn;
row(){}
row(const int &_p,const int &_mx,const int &_mn) {
p=_p;mx=_mx;mn=_mn;
}
};
vector<ii> g[MAX];
int c[MAX];
int l[MAX];
row p[MAX][21];
int n,k;
scanf("%d",&n);
int i,j,u,v,w;
for (i=1;i<=n;i=i+1) {
c[i]=0;
l[i]=0;
g[i].clear();
for (j=0;j<=19;j=j+1) p[i][j]=row(0,0,0);
}
l[0]=-1;
for (i=1;i<n;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
g[u].push_back(ii(v,w));
g[v].push_back(ii(u,w));
}
}
void BFS(void) {
queue<int> q;
while (!q.empty()) q.pop();
c[1]=1;
l[1]=0;
q.push(1);
int i,u;
while (!q.empty()) {
u=q.front();q.pop();
for (i=0;i<g[u].size();i=i+1)
if (c[g[u][i].f]==0) {
c[g[u][i].f]=1;
l[g[u][i].f]=l[u]+1;
p[g[u][i].f][0]=row(u,g[u][i].s,g[u][i].s);
q.push(g[u][i].f);
}
}
}
int max(const int &x,const int &y) {
if (x>y) return (x); else return (y);
}
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
void process(void) {
int i,j;
BFS();
for (j=1;j<=19;j=j+1)
for (i=1;i<=n;i=i+1)
p[i][j]=row(p[p[i][j-1].p][j-1].p,max(p[i][j-1].mx,p[p[i][j-1].p][j-1].mx),min(p[i][j-1].mn,p[p[i][j-1].p][j-1].mn));
}
row lca(int u,int v) {
if (l[u]<l[v]) return (lca(v,u));
int i,mx,mn;
mx=-1e7;mn=1e7;
for (i=19;i>=0;i=i-1)
if (l[p[u][i].p]>=l[v]) {
mx=max(mx,p[u][i].mx);
mn=min(mn,p[u][i].mn);
u=p[u][i].p;
}
if (u==v) return (row(u,mx,mn));
for (i=19;i>=0;i=i-1)
if (p[u][i].p!=p[v][i].p) {
mx=max(mx,max(p[u][i].mx,p[v][i].mx));
mn=min(mn,min(p[u][i].mn,p[v][i].mn));
u=p[u][i].p;
v=p[v][i].p;
}
return (row(p[u][0].p,max(mx,max(p[u][0].mx,p[v][0].mx)),min(mn,min(p[u][0].mn,p[v][0].mn))));
}
int i,a,b;
row p;
scanf("%d",&k);
for (i=1;i<=k;i=i+1) {
scanf("%d",&a);
scanf("%d",&b);
p=lca(a,b);
printf("%d %d\n",p.mn,p.mx);
}
}
int main(void) {
process();
return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> ke[100010], gt[100010];
int fa[100010], tofa[100010], h[100010];
bool vs[100010];

int cha[17][100010], M[17][100010], m[17][100010];

void dfs(int i) {
vs[i] = true;
for(int k=0;k<ke[i].size();++k) {
int j = ke[i][k], c = gt[i][k];
if(!vs[j]) {
h[j] = h[i]+1;
tofa[j] = c;
fa[j] = i;
dfs(j);
}
}
}

void init(int m[][100010], const int& (*f)(const int&,const int&)) {
for(int i=1;i<=n;++i) m[0][i] = tofa[i];
for(int i=1;i<17;++i) {
for(int j=1;j<=n;++j) m[i][j] = f( m[i-1][j], m[i-1][ cha[i-1][j] ] );
}
}

int chachung(int a,int b) {
if(h[a]<h[b]) swap(a,b);
for(int i=16;i>=0;--i) if( cha[i][a]>0 && h[cha[i][a]]>=h[b]) a = cha[i][a];
if(a==b) return a;
for(int i=16;i>=0;--i) if( cha[i][a]>0 && cha[i][b]>0 && cha[i][a]!=cha[i][b]) {
a = cha[i][a];
b = cha[i][b];
}
return fa[a];
}

int process(int u, int len, int m[][100010], const int& (*f)(const int&,const int&), int bd) {
int res = bd;
for(int i=16;i>=0;--i) if(len>=(1<<i)) {
res = f( res, m[i][u]);
u = cha[i][u];
len -= (1<<i);
}
return res;
}

int main() {
scanf("%d", &n);
for(int i=0;i<n-1;++i) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
ke[u].push_back(v);
ke[v].push_back(u);
gt[u].push_back(c);
gt[v].push_back(c);
}
dfs(1);
for(int i=1;i<=n;++i) cha[0][i] = fa[i];
for(int i=1;i<17;++i) for(int j=1;j<=n;++j) cha[i][j] = cha[i-1][  cha[i-1][j] ];
init( M, max<int>);
init( m, min<int>);
int q;
scanf("%d", &q);
for(int i=0;i<q;++i) {
int u, v, c;
scanf("%d%d", &u, &v);
c = chachung(u,v);
int m1 = max( process( u, h[u]-h[c], M, max<int>, 0), process( v, h[v]-h[c], M, max<int>, 0));
int m2 = min( process( u, h[u]-h[c], m, min<int>, 1000000), process( v, h[v]-h[c], m, min<int>, 1000000));
printf("%d %d\n", m2, m1);
}
//system("pause");
return 0;
}