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

const fi='';
      fo='';
      maxn=100010;
var n,s,re,r1,r2,same,max:longint;
    a,b:array[1..maxn shl 1] of longint;
    pos,cur,sl,d,f,g,m1,m2:array[1..maxn] of longint;
    c:array[1..maxn,0..2] of longint;

procedure rf;
var i,p,q:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n,s);
     for i:=1 to n-1 do
     begin
          read(c[i,0],c[i,1],c[i,2]);
          inc(sl[c[i,0]]); inc(sl[c[i,1]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to n-1 do
     begin
          p:=c[i,0]; q:=c[i,1];
          a[cur[p]]:=q; a[cur[q]]:=p; b[cur[p]]:=c[i,2]; b[cur[q]]:=c[i,2];
          inc(cur[p]); inc(cur[q]);
     end;
     close(input);
end;

procedure dfs(x,y:longint);
var i,v:longint;
begin
     for i:=pos[x] to pos[x+1]-1 do
         if a[i]=y then
         begin
              f[x]:=b[i];
              break;
         end;
     d[x]:=1;
     for i:=pos[x] to pos[x+1]-1 do
         if d[a[i]]=0 then
         begin
              dfs(a[i],x);
              f[x]:=f[x]+f[a[i]]+b[i];
              v:=m1[a[i]]+b[i];
              if v>=m1[x] then
              begin
                   m2[x]:=m1[x];
                   m1[x]:=v;
              end
              else
              begin
                   if v>m2[x] then m2[x]:=v;
              end;
              if m1[x]+m2[x]>max then
                 max:=m1[x]+m2[x];
         end;
end;

procedure pr;
var i,j:longint;
begin
     dfs(s,0);
     re:=f[s]-max;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#define FOR(i, a, b) for(int i=(a); i< (b); i++)
#define REP(i, a, b) for(int i=(a); i<=(b); i++)
#define ii pair<int, int>
#define X first
#define Y second
const int N = 100005;
using namespace std;
vector<ii> a[N], child[N];
bool was[N];
int n, root;
int F[N][2][2];

void Init(int u) {
    was[u] = true;
    FOR(i, 0, a[u].size()) {
        int v = a[u][i].X;
        if (!was[v]) {
            Init(v);
            child[u].push_back(ii(v, a[u][i].Y));
        }
    }
    a[u] = child[u];
}

int DP(int u, int bull, int ret) {
    if (F[u][bull][ret] >= 0) return F[u][bull][ret];
    #define v a[u][i]
    if (bull == 1) {
        if (ret == 1) {
            F[u][1][1] = 0;
            FOR(i, 0, a[u].size())
                F[u][1][1] += DP(v.X, 1, 1) + 2 * v.Y;
        }
        else {
            F[u][1][0] = DP(u, 1, 1);
            FOR(i, 0, a[u].size())
                F[u][1][0] = min(F[u][1][0], F[u][1][1] - v.Y - DP(v.X, 1, 1) + DP(v.X, 1, 0));
        }
    }
    else {
        F[u][2][0] = DP(u, 1, 1);
        FOR(i, 0, a[u].size())
            F[u][2][0] = min(F[u][2][0], F[u][1][1] - DP(v.X, 1, 1) + DP(v.X, 2, 0));
        vector<int> P;
        FOR(i, 0, a[u].size())
            P.push_back(DP(v.X, 1, 0) - v.Y - DP(v.X, 1, 1));
        sort(P.begin(), P.end());
        if (P.size() > 1)
            F[u][2][0] = min(F[u][2][0], F[u][1][1] + P[0] + P[1]);
    }
    #undef v
    //cout << u << ' ' << bull << ' ' << ret << ' ' << F[u][bull][ret] << endl;
    return F[u][bull][ret];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> root;
    int u, v, c;
    FOR(i, 1, n) {
        cin >> u >> v >> c;
        a[u].push_back(ii(v, c));
        a[v].push_back(ii(u, c));
    }
    Init(root);
    memset(F, 255, sizeof F);
    cout << DP(root, 2, 0);
    return 0;
}

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;

type
  list          =       ^node;
  node          =       record
        u,c     :       longint;
        next    :       list;
  end;

procedure add(u,c:longint; var a:list); inline;
    var
      p:list;
    begin
      new(p); p^.u:=u; p^.c:=c;
      p^.next:=a; a:=p;
    end;

var
  f1,f2         :       text;
  n             :       longint;
  ke            :       array[1..MAXN] of list;
  f,father      :       array[1..MAXN] of longint;
  res           :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i,u,v,c:longint;
    begin
      read(f1,n,c);
      for i:=1 to n-1 do
        begin
          read(f1,u,v,c);
          add(u,c,ke[v]);
          add(v,c,ke[u]);
        end;
    end;

procedure dfs(u:longint);
    var
      p:list;
      v,c,m1,m2,now:longint;
    begin
      f[u]:=0;
      p:=ke[u]; m1:=0; m2:=0;
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c; p:=p^.next;
          if v=father[u] then continue;
          if f[v]=-1 then
            begin
              father[v]:=u;
              dfs(v);
            end;
          now:=f[v]+c;
          if now>m1 then
            begin
              m2:=m1;
              m1:=now;
            end
          else if now>m2 then
            m2:=now;
        end;
      f[u]:=m1;
      res:=max(res,m1+m2);
    end;

procedure solve;
    var
      i:longint;
      p:list;
    begin
      res:=0;
      fillchar(f,sizeof(f),$FF);
      dfs(1);
      res:=-res;
      for i:=1 to n do
        begin
          p:=ke[i];
          while p<>nil do
            begin
              inc(res,p^.c);
              p:=p^.next;
            end;
        end;
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  if n=1 then writeln(f2,0)
  else solve;
  closeF;
end.

Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, x;
vector<pair<int,int> > ke[100010];
int h[100010];

void dfs(int i, int fi) {
    for(int k=0;k<ke[i].size();++k) {
        int j = ke[i][k].first;
        if(j != fi) {
            h[j] = h[i] + ke[i][k].second;
            dfs(j, i);
        }
    }
}

int main() {
    int total = 0;
    scanf("%d%d", &n, &x);  
    for(int i=1;i<n;++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        total += c;
        ke[u].push_back(make_pair(v,c));
        ke[v].push_back(make_pair(u,c));
    }
    dfs(1, -1);
    int imax = max_element( h + 1, h + 1 + n) - h;
    h[imax] = 0;
    dfs(imax, -1);
    imax = max_element( h + 1, h + 1 + n) - h;
    printf("%d\n", total * 2 - h[imax]);
    return 0;
}