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>
#include <cstdio>
#include <vector>
#define N 100100
using namespace std;

int n,money,re,maxDist[N],distFrom1[N];
vector <int> a[N],c[N],cMin[N];

void init(int x,int par)
{
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (y!=par) 
        {
            init(y,x);
            maxDist[x]=max(maxDist[x],maxDist[y]+c[x][i]);
        }
    }
}

int visit(int x,int par,int &money,int val)
{
    if (par && a[x].size()==1) return distFrom1[x]<=val?1:0;
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (y!=par) 
        {
            int need=max(0,maxDist[y]+distFrom1[x]+c[x][i]-val);
            if (need<=c[x][i]-cMin[x][i])
            {
                if (money<need) return 0;
                money-=need;
            }
            else
            {
                need=c[x][i]-cMin[x][i];
                if (money<need) return 0;
                money-=need;
                distFrom1[y]=distFrom1[x]+cMin[x][i];
                if (!visit(y,x,money,val)) return 0;
            }
        }
    }
    return 1;
}

int main()
{
    int x,y,z,t;
    cin >> n >> money;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d%d",&x,&y,&z,&t);
        a[x].push_back(y); c[x].push_back(z); cMin[x].push_back(t);
        a[y].push_back(x); c[y].push_back(z); cMin[y].push_back(t);
    }
    init(1,0);
    int low=0,high=2000000000;
    while (low<=high)
    {
        int mid=(low+high)/2,tmp=money;
        if (visit(1,0,tmp,mid)) re=mid, high=mid-1;
        else low=mid+1;
    }
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 100500;
const int oo = trunc(1e9);
using namespace std;
int n, k, money, m, res;
bool visit[N];
int d[N];
vector<iii> a[N], child[N];

void DFS(int u) {
    //the function holds the responsibility to determine u 's descendants
    visit[u] = true; d[u] = 0;
    iii v;
    for(int i=0; i<a[u].size(); i++) {
        v = a[u][i];
        if (!visit[v.X]) {
            child[u].push_back(v);
            DFS(v.X);
            d[u] = max(d[u], d[v.X] + v.Y.X);
        }
    }
}

bool Reduce(int u, int dis) {
    //after some reduction, distance from 1 to u is now dis
    //our target is to reduce u 's adjacent edges to make d[u] + dis <= m
    //if the target can be achieved, the function returns true
    if (d[u] + dis <= m) return true;
    else if (child[u].size() == 0) return false;
    int v, now, lim, target, delta, diff;
    for(int i=0; i<child[u].size(); i++) {
        v = child[u][i].X;
        now = child[u][i].Y.X;
        lim = child[u][i].Y.Y;
        //d[v] + target + dis <= m
        // =>
        target = m - dis - d[v];
        if (target >= now) continue;
        //let 's see how far can we reduce this edge
        delta = now - target;
        if (target >= lim) {
            if (delta <= money) {
                money -= delta;
                continue;
            }
            else
                return false;
        }
        else {
            //now we have to continue our job on the children
            diff = now - lim;
            if (diff > money) return false;
            money -= diff;
            if (!Reduce(v, lim + dis)) return false;
        }

    }
    return true;
}

int main()
{
    scanf("%d %d\n", &n, &k);
    int u, v, x, y;
    for(int i=1; i<n; i++) {
        scanf("%d %d %d %d\n", &u, &v, &x, &y);
        a[u].push_back(iii(v, ii(x, y)));
        a[v].push_back(iii(u, ii(x, y)));
    }
    DFS(1);
    //binary search the answer
    int l = 0, r = oo;
    while (l <= r) {
        m = (l + r) / 2;
        money = k;
        if (Reduce(1, 0)) {
            res = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define P pair<int,int>
#define PP pair< int,P >
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define MAXN 100111
using namespace std;

int debug=0;
int n,k,f[MAXN],father[MAXN];
vector< PP > ke[MAXN];

void inp() {
    scanf("%d %d",&n,&k);
    FOR(i,1,n-1) {
        int x,y,a,b;
        scanf("%d %d %d %d",&x,&y,&a,&b);
        ke[x].PB(MP(y,MP(a,b)));
        ke[y].PB(MP(x,MP(a,b)));
    }
}

void dfs1(int u) {
    f[u]=0;
    FORV(now,ke[u]) {
        int v=now->F, a=now->S.F;
        if (f[v]>=0) continue;
        dfs1(v);
        father[v]=u;
        f[u] >?= f[v]+a;
    }
}

int get(int u,int gh) {
    int res=0;
    if (gh<0) return k+1;
    FORV(now,ke[u]) {
        int v = now->F, a = now->S.F, b = now->S.S;
        if (father[u]==v) continue;
        if (a+f[v]<=gh) res+=0;
        else if (b+f[v]<=gh) res+=a+f[v]-gh;
        else res+=a-b+get(v,gh-b);
        if (res>k) return k+1;
    }
    if (res>k) res=k+1;
    return res;
}

void solve() {
    memset(f,-1,sizeof f);
    dfs1(1);
    if (debug) {
        FOR(i,1,n) cout<<f[i]<<" "; 
        cout<<endl;
    }

    int l=0,r=1000111000, res;
    while (l<=r) {
        int mid=(l+r)>>1;
        if (get(1,mid)<=k) {
            res=mid;
            r=mid-1;
        } else l=mid+1;
    }
    cout<<res;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}


typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;

// Dinic

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

#define maxn 100005
#define maxe 200005

int f[maxn], adj[maxe], next[maxe], last[maxn];
int A[maxe], B[maxe];
int n, Money, E = 0, M, Dist;

void add(int u, int v, int MaxC,int MinC){
    adj[E] = v; next[E] = last[u]; A[E] = MaxC; B[E] = MinC; last[u] = E++;
    adj[E] = u; next[E] = last[v]; A[E] = MaxC; B[E] = MinC; last[v] = E++;
}

void duyet1(int par, int u){
    f[u] = 0;
    for(int e = last[u]; e != -1; e = next[e]) if(adj[e] != par){
        int v = adj[e];
        duyet1(u, v);
        f[u] = max(f[u],f[v] + A[e]);
    }
}

bool duyet(int L, int mother, int u){
    if(u == 1) L = 0;
    else if(L + A[mother] + f[u] <= Dist)
        L += A[mother];
    else if(L + B[mother]  + f[u] <= Dist){
        M -= L + A[mother] + f[u] - Dist;
        L = Dist - f[u];
    }    
    else{
        M -= A[mother] - B[mother];
        L += B[mother];
    }
    if(L > Dist) return false;

    bool flag = true;
    for(int e = last[u]; e != -1; e = next[e]) if(e != (mother ^ 1)){
        int v = adj[e];
        flag &= duyet(L, e, v);
    }

    return flag;
}

int main(){
   // OPEN();
    int u, v, MaxC, MinC;
    memset(last, -1 ,sizeof(last));
    gi(n); gi(Money);
    rep(i, n - 1){
        gi(u); gi(v); gi(MaxC); gi(MinC);
        add(u, v, MaxC, MinC);
    }
    duyet1(0, 1);
    int left = 0, right = oo, mid;
    while(left < right){
        mid = (left + right) >> 1;
        M = Money; Dist = mid;
        if(duyet(0, -1, 1) && M >= 0){
            right = mid;
        }
        else left = mid + 1;
    }
    printf("%d",left);
}

Code mẫu của ll931110

{$R+,Q}
{$MODE DELPHI}
program MROADS;
const
  fin = '';
  fou = '';
  maxn = 100000;
  maxv = 10000 * 10000;
type
  pnode = ^tnode;
  tnode = record
    node,cost,best: integer;
    link: pnode;
  end;
var
  a: array[1..maxn] of pnode;
  top,bot,b2,pr: array[1..maxn] of integer;
  free: array[1..maxn] of boolean;
  n,k: integer;
  mid,res,money: integer;
  flag: boolean;

procedure add(x,y,c,b: integer);
var
  p: pnode;
begin
  new(p);
  p^.node := y;
  p^.cost := c;
  p^.best := b;
  p^.link := a[x];
  a[x] := p;
end;

procedure init;
var
  f: text;
  i,x,y,c,b: integer;
begin
  assign(f, fin);
    reset(f);

  readln(f, n, k);
  for i := 1 to n do a[i] := nil;

  for i := 1 to n - 1 do
    begin
      readln(f, x, y, c, b);
      add(x,y,c,b);
      add(y,x,c,b);
    end;

  close(f);

  fillchar(free, sizeof(free), true);
  fillchar(top, sizeof(top), 0);
  fillchar(bot, sizeof(bot), 0);
  fillchar(b2, sizeof(b2), 0);

  pr[1] := -1;
end;

procedure DFS(u: integer);
var
  p: pnode;
  v: integer;
begin
  free[u] := false;
  p := a[u];
  while p <> nil do
    begin
      v := p^.node;
      if free[v] then
        begin
          pr[v] := u;
          top[v] := top[u] + p^.best;
          DFS(v);
        end;

      if v <> pr[u] then
        begin
          if bot[u] < bot[v] + p^.cost then bot[u] := bot[v] + p^.cost;
          if b2[u] < b2[v] + p^.best then b2[u] := b2[v] + p^.best;
        end;

      p := p^.link;
    end;
end;

procedure upgrade(u: integer);
var
  p: pnode;
  v,rep: integer;
begin
  if top[u] + b2[u] > mid then
    begin
      flag := false;
      exit;
    end;

  if not flag then exit;
  p := a[u];

  while p <> nil do
    begin
      v := p^.node;
      if v <> pr[u] then
        begin
          if top[u] + p^.cost + bot[v] > mid then
            begin
              rep := top[u] + bot[v] + p^.cost - mid;
              if rep > p^.cost - p^.best then rep := p^.cost - p^.best;
              money := money - rep;
            end;

          if money < 0 then
            begin
              flag := false;
              exit;
            end;

          if top[v] + bot[v] > mid then upgrade(v);
        end;
      p := p^.link;
    end;
end;

procedure solve;
var
  inf,sup: integer;
begin
  inf := 0;
  sup := maxv;

  repeat
    mid := (inf + sup) div 2;
    flag := true;
    money := k;
    upgrade(1);

    if flag then
      begin
        res := mid;
        sup :=  mid - 1;
      end
    else inf := mid + 1;
  until inf > sup;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, fou);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  DFS(1);
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
struct Edge {
    int u,v,fstC,minC;
    Edge() {
        u=v=fstC=minC=0;
    }
    void input(void) {
        scanf("%d%d%d%d",&u,&v,&fstC,&minC);
    }
    inline int other(int x) const {
        return (u^v^x);
    }
};
vector<int> g[MAX];
Edge edge[MAX];
int maxH[MAX],par[MAX];
int limCost,n;
void loadtree(void) {
    scanf("%d%d",&n,&limCost);
    REP(i,n-1) {
        edge[i].input();
        g[edge[i].u].push_back(i);
        g[edge[i].v].push_back(i);
    }
}
int fstVisit(int u) {
    REP(i,g[u].size()) {
        int v=edge[g[u][i]].other(u);
        if (v!=par[u]) {
            par[v]=u;
            fstVisit(v);
            maxH[u]=max(maxH[u],maxH[v]+edge[g[u][i]].fstC);
        }
    }
}
int usedCost(int u,int dis,int limH) {
    if (dis>limH) return (limCost+1);
    if (dis+maxH[u]<=limH) return (0);
    int res=0;
    REP(i,g[u].size()) {
        Edge &cur=edge[g[u][i]];
        int v=cur.other(u);
        if (v!=par[u] && dis+cur.fstC+maxH[v]>limH) {
            int redu=min(cur.fstC-cur.minC,dis+cur.fstC+maxH[v]-limH);
            res+=redu+usedCost(v,dis+cur.fstC-redu,limH);
            if (res>limCost) return (limCost+1);
        }
    }
    return (min(res,limCost+1));
}
void process(void) {
    int L=0;
    int R=INF;
    while (true) {
        if (L==R) {
            printf("%d",R);
            return;
        }
        if (R-L==1) {
            if (usedCost(1,0,L)<=limCost) printf("%d",L); else printf("%d",R);
            return;
        }
        int M=(L+R)>>1;
        if (usedCost(1,0,M)<=limCost) R=M; else L=M+1;
    }
}
int main(void) {
    loadtree();
    fstVisit(1);
    process();
    return 0;
}

Code mẫu của khuc_tuan

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

struct Node {
    int v, len, minlen;
    Node * next;
};

int n, k;
Node * ke[100010];
bool vs[100010];
int H[100010], L[100010], fa[100010];
int q[100010], nq;

int main() {
    scanf("%d%d", &n, &k);
    for(int i=1;i<n;++i) {
        int u, v, a, b;
        scanf("%d%d%d%d", &u, &v, &a, &b);
        #define add(p,a,b,c) {Node*q=new Node;q->v=a;q->len=b;q->minlen=c;q->next=p;p=q;}
        add( ke[u], v, a, b);
        add( ke[v], u, a, b);
    }   
    q[nq++] = 1;
    vs[1] = true;
    for(int t=0;t<nq;++t) {
        int u = q[t];
        for(Node *p=ke[u];p!=NULL;p=p->next) {
            int v = p->v;
            if(!vs[v]) {
                fa[v] = u;
                vs[v] = true;
                q[nq++] = v;
            }
        }
    }
    for(int t=nq-1;t>=0;--t) {
        int u = q[t];
        H[u] = 0;
        for(Node*p=ke[u];p!=NULL;p=p->next) {
            int v = p->v;
            if(fa[v] == u) H[u] = max( H[u], H[v] + p->len);
        }   
    }
    int low = 0, high = H[1];
    while(low < high) {
        int M = (low + high) / 2;
        // check M
        bool OK = true;
        int rem = k;
        L[1] = 0;
        for(int t=0;t<nq;++t) {
            int u = q[t];
            bool isleaf = true;
            for(Node*p=ke[u];p!=NULL;p=p->next) {
                int v = p->v;
                if(fa[v] == u) {
                    isleaf = false;
                    if(L[u] + H[v] + p->len > M) {
                        int newlen = M - L[u] - H[v];
                        newlen = max(newlen, p->minlen);
                        newlen = max(newlen, p->len - rem);
                        rem -= p->len - newlen;
                        L[v] = L[u] + newlen;
                    }   
                    else L[v] = L[u] + p->len;
                }
            }
            if(isleaf && L[u] > M) OK = false;
        }

        if(OK) high = M;
        else low = M + 1;
    }
    printf("%d\n", low);
    // system("pause");
    return 0;
}