/*
Author: AkiYuu
TASK:
LANG: C++14
*/
#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
using namespace std;
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
}
const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;
vector < ii > a[mxn];
int up[20][mxn], tin[mxn], tout[mxn], timer;
ll add[mxn];
int n;
ll cost[2][mxn];
int edge[mxn];
ll ans = 0;
void dfs(int u, int p ){
tin[u] = ++timer;
up[0][u] = p;
for ( ii x : a[u]){
int v = x.first, id = x.second;
if ( v == p ) continue;
dfs(v,u);
edge[v] = id;
}
tout[u] = timer;
}
bool ispar(int u , int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if (ispar(u,v) ) return u;
if (ispar(v,u) ) return v;
fbw(i,18,0) if (!ispar(up[i][u], v)) u= up[i][u];
return up[0][u];
}
void get(int u, int p = -1){
for ( ii x : a[u]) {
int v = x.first, id = x.second;
if (v == p ) continue;
get(v,u);
add[u] += add[v];
}
int Eid = edge[u];
ans += min( cost[0][Eid] * add[u], cost[1][Eid] );
}
void solve(){
cin >> n;
ffw(i,1,n-1){
int u , v;
cin >> u >> v >> cost[0][i] >> cost[1][i];
a[u].pb(ii(v,i));
a[v].pb(ii(u,i));
}
dfs(1,1);
ffw(i,1,18) ffw(j,1,n){
up[i][j] = up[i-1][ up[i-1][j] ];
}
s
ffw(i,1,n-1){
int u = i, v = i +1, c= lca(u,v);
add[u]++;
add[v]++;
add[c] -= 2;
}
get(1);
cout << ans;
}
int main(){
fastio();
int t = 1;
// cin >> t;
while (t--)
solve();
}
Compilation message
putovanje.cpp: In function 'void get(int, int)':
putovanje.cpp:70:26: warning: unused variable 'id' [-Wunused-variable]
70 | int v = x.first, id = x.second;
| ^~
putovanje.cpp: In function 'void solve()':
putovanje.cpp:95:5: error: 's' was not declared in this scope
95 | s
| ^
putovanje.cpp:96:9: error: 'i' was not declared in this scope
96 | ffw(i,1,n-1){
| ^
putovanje.cpp:14:35: note: in definition of macro 'ffw'
14 | #define ffw(i,a,b) for (ll i = a; i <= b; i++)
| ^
