LUBENICA – spoj

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end

VOTREE – spoj

Đề bài:

Giải thích ví dụ

votree-yeulaptrinh
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.

Thuật toán:

    Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.

    Các phần cơ bản của cây IT:

    IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.

    IT[id] = LCA(IT[id*2],IT[id*2+1] ).

    P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …

Code:

const
        tfi='';
        tfo='';
 
var
        fi,fo:Text;
        ke,nx:array[-70000..70000] of longint;
        num,thoat,hd:array[0..70000] of longint;
        f:array[0..70000,0..20] of longint;
        n,q,jmax,dem,dem1:longint;
        t:array[0..3000000] of longint;
 
procedure nhap;
        var i,j,u,v:longint;
        begin
                read(fi,n,q);
                for i:=1 to n-1 do
                        begin
                                read(fi,u,v);
                                ke[i]:=v;
                                nx[i]:=hd[u];
                                hd[u]:=i;
                                ke[-i]:=u;
                                nx[-i]:=hd[v];
                                hd[v]:=-i;
                        end;
                for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
        end;
 
procedure DFS(u:longint);
        var j,v:longint;
        begin
                inc(dem);
                num[u]:=dem;
                for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
                j:=hd[u];
                while j<>0 do
                        begin
                                v:=ke[j];
                                if f[v,0]=0 then
                                        begin
                                                f[v,0]:=u;
                                                DFS(v);
                                        end;
                                j:=nx[j];
                        end;
                inc(dem1);
                thoat[u]:=dem1;
        end;
 
function cha(x,y:longint):boolean;
        begin
            cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
        end;
 
function lca(x,y:longint):longint;
        var j:longint;
        begin
                if cha(x,y) then exit(x);
                if cha(y,x) then exit(y);
                for j:=jmax downto 0 do
                        if not cha(f[x,j],y) then x:=f[x,j];
                exit(f[x,0]);
        end;
 
procedure init(i,l,r:longint);
        var mid:longint;
        begin
            if l=r then
                begin
                        t[i]:=l;
                        exit;
                end;
            mid:=(l+r) div 2;
            init(i*2,l,mid);
            init(i*2+1,mid+1,r);
            t[i]:=lca(t[i*2],t[i*2+1]);
        end;
 
function get(i,l,r,u,v:longint):longint;
        var mid:longint;
        begin
                if (l>v) or (r<u) then exit(u);
                if (u<=l) and (r<=v) then exit(t[i]);
                mid:=(l+r) div 2;
                get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
        end;
 
procedure xuli;
        var i,u,v,pa,j:longint;
        begin
                f[1,0]:=1;
                DFS(1);
                init(1,1,n);
                for i:=1 to q do
                        begin
                                read(fi,u,v);
                                writeln(fo,get(1,1,n,u,v));
                        end;
 
        end;
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

PWALK – spoj

Đề bài:

Thuật toán:

  • DFS để thiết lập thứ tự cha/con rồi với mỗi truy vấn chỉ cần đi ngược lên đến khi gặp cha chung thì dừng.

Code:

#include <iostream>
#include <vector>
using namespace std;
 
struct pack { int u, c; };
typedef vector<vector<pack>> dsk;
 
int d[1001], bac[1001], cha[1001];
 
void dfs(int u, const dsk &ke) {
    for (pack p: ke[u]) if (p.u != cha[u]) {
        int v = p.u, c = p.c;
        d[v] = c;
        cha[v] = u;
        bac[v] = bac[u] + 1;
        dfs(v, ke);
    }
}
 
int solve(int u, int v) {
#define up(u) sum += d[u], u = cha[u]
    int sum = 0;
    while (bac[u] > bac[v]) up(u);
    while (bac[v] > bac[u]) up(v);
    while (u != v) up(u), up(v);
    return sum;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    dsk ke(n+1);
    for (int i=1; i<n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ke[u].push_back({v, c});
        ke[v].push_back({u, c});
    }
    dfs(1, ke);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << solve(u, v) << '\n';
    }
    return 0;
}

UPGRANET – spoj

Đề bài:


Thuật toán:


Ta thấy thông lượng truyền tin từ u đến v là giá trị lớn nhất của cạnh nhỏ nhất trên mọi con đường từ u đến v.
Vì vậy, ban đầu, ta sẽ xây dựng cây khung lớn nhất(tương tự như cây khung nhỏ nhất nhưng sort ngược lại).

Gọi dis(u,v) là cạnh có trọng số nhỏ nhất khi đi từ u đến v trên cây vừa tạo. Ta chọn nút 1 làm gốc, duyệt dfs để lưu trữ cạnh nhỏ nhất và các nút cha của u khi đi từ 1 đến u (đều dùng RMQ). Với mỗi 1 cạnh không nằm trong cây khung, ta tìm nút cha chung gần nhất(gọi là p), kết quả cộng thêm một lượng bằng hiệu của min(dis(u, p), dis(v, p)) và rọng số cạnh đang xét.

Code:


#include <bits/stdc++.h>
#define maxn 1000005
#define maxm 10000005
#define maxc 1000000007
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair<long long, long long>
#define fort(i, a, b) for(int i = (a); i <= (b); i++)
#define ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Task "UPGRANET"
#define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define stop1 {cout << "-1\n"; return;}
#define stop2 {cout << "0\n"; return;}
#define stop3 {cout << "yes\n"; exit(0);}
#define skip1 {cout << "Yes\n"; continue;}
#define skip2 {cout << "No\n"; continue;}
#define ll long long
 
using namespace std;
 
ll n, m, root[maxn], h[maxn], res;
pii  par[maxn][20];
bool dd[maxn];
vector<pair<ll, ll> > ke[maxn];
struct canh
{
    ll u, v, w;
}ed[maxn];
 
void setup()
{
    cin >> n >> m;
    fort(i, 1, m)
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
}
 
bool cmp(canh p, canh q)
{
    return p.w > q.w;
}
 
ll getroot(ll u)
{
    if(root[u] == 0) return u;
    return root[u] = getroot(root[u]);
}
 
void make_tree()
{
    sort(ed+1, ed+m+1, cmp);
    fort(i, 1, m)
    {
        ll p = getroot(ed[i].u);
        ll q = getroot(ed[i].v);
        if(p == q) continue;
        root[p] = q;
        dd[i] = 1;
        ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
        ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
    }
}
 
void dfs(ll u, ll tr)
{
    fort(i, 0, int(ke[u].size()) - 1)
    {
        ll v = ke[u][i].F;
        if(v == tr) continue;
        h[v] = h[u] + 1;
        par[v][0] = mp(u,ke[u][i].S);
        fort(j, 1, 18)
        {
            par[v][j].F = par[par[v][j-1].F][j-1].F;
            par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
        }
        dfs(v, u);
    }
}
 
pii lca(ll u, ll v)
{
    pii p;
    p.S = 1ll* maxc * maxc;
    if( h[u] > h[v])
        swap(u, v);
    ll diff = h[v] - h[u];
    ford(i, 18, 0)
        if((diff >> i) & 1)
        {
            p.S = min(p.S, par[v][i].S);
            v = par[v][i].F;
 
        }
    if(v == u) return mp(u, p.S);
    ford(i, 18, 0)
        if(par[u][i].F != par[v][i].F)
        {
            p.S = min(p.S, min(par[v][i].S, par[u][i].S));
            v = par[v][i].F;
            u = par[u][i].F;
        }
    return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
}
 
void work()
{
    make_tree();
    h[1] = 1;
    dfs(1, 0);
    fort(i, 1, m)
        if(!dd[i])
        {
            pii l = lca(ed[i].u, ed[i].v);
            res += max(0ll, l.S - ed[i].w);
        }
    cout << res;
}
 
 
int main()
{
    fast
  //  freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    work();
    return 0;
}

Cowboy

C11BC2 – spoj

Đề bài:

Thuật toán:

  • Bài này chỉ cần LCA thôi. Dễ mà bạn tự nghĩ sẽ ra…

Code:

const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxm=trunc(1e5);
  maxp=20;
var
  link,head,ke,ts : array[-maxm..maxm] of longint;
  i,j,n,m,x,y,q,qq : longint;
  depth,cha,cau : array[1..maxn] of longint;
  p : array[1..maxn,0..maxp] of longint;
  ok : array[1..maxn,0..maxp] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v,w : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
    ts[i] := w;
  end;
procedure enter;
  var u,v ,w :longint;
  begin
    assign(input,fi);reset(input);
    readln(n,q);
    for i:=2 to n do
      begin
        read(v,w);
        add(i,i,v,w);
        add(-i,v,i,w);
      end;
  end;
procedure dfs(u : longint);
  var i,j,v : longint;
  begin
    cx[u] := false;
    i:=head[u];
    while i<>0 do
      begin
        v:=ke[i];
        if cx[v] then
        begin
          cau[v] := i;
          cha[v] := u;
          depth[v] := depth[u]+1;
          dfs(v);
        end;
        i:=link[i];
      end;
  end;
procedure init;
  var i,u : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    cha[1] := 1;
    depth[1] := 1;
    dfs(1);
    for i:=1 to n do
      begin
        p[i,0] := cha[i];
        if cau[i]<>0 then
          if ts[cau[i]]=2 then
            ok[i,0] := true;
      end;
      for i:=1 to maxp do
      for u:=1 to n do
        begin
          p[u,i] := p[p[u,i-1],i-1];
          ok[u,i] := ok[u,i] or ok[u,i-1] or ok[p[u,i-1],i-1];
        end;
  end;
function lca ( u,v : longint) : boolean;
  var res : boolean;
  begin
    res := false;
    for i:=maxp downto 0 do
      if depth[p[u,i]]>=depth[v] then
        begin
          res := res or ok[u,i];
          u := p[u,i];
        end;
    for i:=maxp downto 0 do
      if depth[p[v,i]]>=depth[u] then
        begin
          res := res or ok[v,i];
          v := p[v,i];
        end;
    if u=v then
      begin
        //writeln(u);
        exit(res);
      end;
        for i:=maxp downto 0 do
          if p[u,i]<>p[v,i] then
          begin
            res := res or ok[u,i];
            res := res or ok[v,i];
            u := p[u,i];
            v := p[v,i];
          end;
    res := res or (ok[u,0]) or (ok[v,0]);
    //writeln(cha[u]);
    exit(res);
end;
procedure process;
  var x,y : longint;
  begin
    assign(output,fo);rewrite(output);
    for qq := 1 to q do
      begin
        read(x,y);
        if lca(x,y) then writeln('YES') else writeln('NO');
      end;
    close(output);
  end;
begin
  enter;
  init;
  process;
end.

HBTLCA – SPOJ

Đề bài: http://vn.spoj.com/problems/HBTLCA/

Thuật toán:

  • (đang cập nhập)

Code:

const
    tfi='';//hbtlca.inp';
    tfo='';//hbtlca.out';
 
var
    fi,fo:Text;
    n,jmax,dem1,goc,dem2:longint;
    ke,nx:array[-100000..100000] of longint;
    hd,num,thoat,d:array[0..100000] of longint;
    f:array[0..100000,0..20] of longint;
 
procedure nhap;
    var i,u,v:longint;
    begin
        read(fi,n);
        fillchar(hd,sizeof(hd),0);
        for i:=1 to n-1 do
            begin
                read(fi,u,v);
                ke[i]:=v;
                nx[i]:=hd[u];
                hd[u]:=i;
                ke[-i]:=u;
                nx[-i]:=hd[v];
                hd[v]:=-i;
            end;
        for i:=0 to 20 do if 1 shl i<=n then jmax:=i+1;
    end;
 
procedure DFS(u:longint);
    var i,j,v:longint;
    begin
        inc(dem1);
        num[u]:=dem1;
        for j:=1 to jmax do
            f[u,j]:=f[f[u,j-1],j-1];
        j:=hd[u];
        while j<>0 do
            begin
                v:=ke[j];
                if v<>f[u,0] then
                    begin
                        f[v,0]:=u;
                        d[v]:=d[u]+1;
                        DFS(v);
                    end;
                j:=nx[j];
            end;
        inc(dem2);
        thoat[u]:=dem2;
    end;
 
function cha(x,y:longint):boolean;
    begin
        cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
    end;
 
function lca(x,y:longint):longint;
    var j:longint;
    begin
        if cha(x,y) then exit(x);
        if cha(y,x) then exit(y);
        for j:=jmax downto 0 do
            if not cha(f[x,j],y) then x:=f[x,j];
        exit(f[x,0]);
    end;
 
procedure check(u,v:longint);
    var pa,pa1,pa2:longint;
    begin
        pa:=lca(u,v);
        pa1:=lca(goc,u);
        pa2:=lca(goc,v);
        if (d[pa]>=d[pa1]) and (d[pa]>=d[pa2]) then writeln(fo,pa)
        else
        if (d[pa1]>=d[pa2]) and (d[pa1]>=d[pa]) then writeln(fo,pa1)
        else writeln(fo,pa2);
    end;
 
procedure xuli;
    var i,j,q,u,v:longint;
        ch:char;
    begin
        while true do
        begin
        nhap;
        if n=0 then exit;
        dem1:=0;
        dem2:=0;
        f[1,0]:=1;
        DFS(1);
        readln(fi,q);
        goc:=1;
        for i:=1 to q do
            begin
                read(fi,ch);
                if ch='!' then
                    begin
                        readln(fi,goc);
                    end
                else
                if ch='?' then
                    begin
                        readln(fi,u,v);
                        check(u,v);
                    end;
            end;
        end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    xuli;
    close(fo);
end.