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;
}

Code mẫu của ladpro98

program lubenica;
uses    math;
type    e=record
        v,w,link:longint;
        end;
const   maxn=100009;
        fi='';
var     adj:array[0..2*maxn] of e;
        head,q,d,cha,w:array[0..maxn] of longint;
        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);
        readln(inp,n);
        for i:=1 to n-1 do
        begin
                readln(inp,x,y,w);
                inc(m);
                adj[m].v:=y;
                adj[m].w:=w;
                adj[m].link:=head[x];
                head[x]:=m;
                inc(m);
                adj[m].v:=x;
                adj[m].w:=w;
                adj[m].link:=head[y];
                head[y]:=m;
        end;
        readln(inp,k);
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);
                i:=head[u];
                while i>0 do
                begin
                        v:=adj[i];
                        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;
                        i:=v.link;
                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
                readln(inp,u,v);
                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> a[MN];                 // adjacency list
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;
    link: pnode;
  end;

  plist = ^tlist;
  tlist = record
    val,nlist: integer;
    link: plist;
  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;

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

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

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

  readln(fi, k);
  for i := 1 to k do
    begin
      readln(fi, u, v);
      t1[i] := u;
      t2[i] := v;
      addlist(u,v,i);
      addlist(v,u,i);
    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;

procedure link(u,v: integer);
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
  link(findset(u),findset(v));
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;
      p := p^.link;
    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)];
      q := q^.link;
    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;

procedure answer(i,low,high: integer);
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,low,mid);
  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;

      p := p^.link;
    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;

      q := q^.link;
    end;
end;



procedure addnewlist(u,v,i: integer);
var
  p: plist;
begin
  new(p);
  p^.val := v;
  p^.nlist := i;
  p^.link := newlist[u];
  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
      addnewlist(t1[i],anclist[i],2 * i);
      addnewlist(t2[i],anclist[i],2 * i + 1);
    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;
void loadgraph(void) {
    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))));
}
void answer(void) {
    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) {
    loadgraph();
    process();
    answer();
    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;
}