lca + 树上差分 求条，玄关

link

代码：

#include <bits/stdc++.h>
#define rep(i ,m ,n) for (int i = (m) ;i <= (n) ;i ++)
#define IOS ios :: sync_with_stdio(0) ;cin.tie (0) ;cout.tie (0)
using namespace std ;
const int N = 2e5 + 7 ;
int n ,dep[N] ,fa[22][N] ,head[N << 2] ,tot ,c[N] ;
long long ans ;
struct edge {
    int to ,nxt ,one ,two ;
}e[N << 2] ;
namespace kafka {
    inline void add (int u ,int v ,int one ,int two) {
        e[++ tot].to = v ;
        e[tot].nxt = head[u] ;
        e[tot].one = one ;
        e[tot].two = two ;
        head[u] = tot ;
    }
    inline void work (int cur ,int f) {
        dep[cur] = dep[f] + 1 ;
        fa[0][cur] = f ;
        rep (i ,1 ,17) {
            fa[i][cur] = fa[i - 1][fa[i - 1][cur]] ;
        }
        for (int i = head[cur] ;i ;i = e[i].nxt) {
            int nex = e[i].to ;
            if (nex == f) goto there ;
            kafka :: work (nex ,cur) ;
            there :
                    ;
        }
    }
    inline int get_lca (int u ,int v) {
        if (u == v) return u ;
        if (dep[u] < dep[v]) swap (u ,v) ;
        for (int i = 17 ;i != -1 ;i --) {
            if (dep[fa[i][u]] >= dep[v]) {
                u = fa[i][u] ;
            }
        }
        if (u == v) return u ;
        for (int i = 17 ;i != -1 ;i --) {
            if (fa[i][u] != fa[i][v]) {
                u = fa[i][u] ;
                v = fa[i][v] ;
            }
        }
        return fa[0][u] ;
    }
    inline void dfs (int cur ,int f) {
        for (int i = head[cur] ;i ;i = e[i].nxt) {
            int nex = e[i].to ;
            if (nex == f) goto there ;
            dfs (nex ,cur) ;
            c[cur] += c[nex] ;
            there :
                    ;
        }
    }
}
int main () {
    IOS ;
    cin >> n ;
    rep (i ,1 ,n - 1) {
        int u ,v ,a ,b ;
        cin >> u >> v >> a >> b ;
        kafka :: add (u ,v ,a ,b) ;
        kafka :: add (v ,u ,a ,b) ;
    }
    kafka :: work (1 ,0) ;
    rep (i ,1 ,n - 1) {
        int anc = kafka :: get_lca (i ,i + 1) ;
        c[i] ++ ;
        c[i + 1] ++ ;
        c[anc] -= 2 ;
    }
    kafka :: dfs (1 ,0) ;
    rep (i ,1 ,n) {
        if (e[i].one * c[i] > e[i].two) {
            ans += e[i].two ;
            goto there ;
        }
        ans += 1ll * e[i].one * c[i] ;
        there :
                ;
    }
    cout << ans << endl ;
    return 0 ;
}