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