#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define MOD 1000000007
typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
const ll INF=63;
const int mxn=2e5+5;
bool DEBUG=0;
int n;
vector<ii>adj[mxn];
ll c[mxn][2];
int cnt[mxn],cnt2[mxn],par[18][mxn],dep[mxn];
void dfs(int u, int p){
for(ii x:adj[u]){
int v=x.fi;
if(v==p)continue;
par[0][v]=u;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int lca(int u, int v){
if(dep[u]<dep[v])swap(u,v);
int dif = dep[u]-dep[v];
for(int i=0; i<18; i++){
if(dif>>i&1)u=par[i][u];
}
if(u==v)return u;
for(int i=17; i>=0; i--){
if(par[i][u]!=par[i][v]){
u=par[i][u];
v=par[i][v];
}
}
return par[0][u];
}
void dfs2(int u, int p){
for(ii x:adj[u]){
int v=x.fi;
int ind=x.se;
if(v==p)continue;
dfs2(v,u);
cnt2[ind]=cnt[v];
cnt[u]+=cnt[v];
}
}
void solve(int u, int v){
int LCA = lca(u,v);
cnt[u]++;
cnt[v]++;
cnt[LCA]-=2;
/*
cerr<<u<<" "<<LCA<<": \n";
for(int i=1; i<=n; i++){
cerr<<i<<" "<<cnt[i]<<"\n";
}
*/
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
cin>>n;
for(int i=0; i<n-1; i++){
int u,v;
cin>>u>>v>>c[i][0]>>c[i][1];
adj[u].eb(v,i);
adj[v].eb(u,i);
}
dep[1]=1;
dfs(1,0);
for(int i=1; i<18; i++){
for(int j=1; j<=n; j++){
if(par[i-1][j]){
par[i][j]=par[i-1][par[i-1][j]];
}
}
}
for(int i=1; i<=n-1; i++)solve(i,i+1);
/*
int LCA = lca(n,1);
cnt[n]--; cnt[1]--;
cnt[LCA]+=2;
for(int i=1; i<=n; i++){
cerr<<i<<" "<<cnt[i]<<"\n";
}
*/
dfs2(1,0);
/*
for(int i=1; i<=n; i++){
cerr<<i<<" "<<cnt[i]<<"\n";
}
*/
ll ans=0ll;
for(int i=0; i<n-1; i++){
if(cnt2[i]){
ll p1=1ll*cnt2[i]*c[i][0];
if(p1<=c[i][1]){
ans+=p1;
}else{
ans+=c[i][1];
}
}
}
cout<<ans;
}
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
5 ms |
5376 KB |
Output is correct |
4 |
Correct |
5 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5248 KB |
Output is correct |
9 |
Correct |
5 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
22520 KB |
Output is correct |
2 |
Correct |
119 ms |
23876 KB |
Output is correct |
3 |
Correct |
119 ms |
26360 KB |
Output is correct |
4 |
Correct |
136 ms |
25852 KB |
Output is correct |
5 |
Correct |
4 ms |
5248 KB |
Output is correct |
6 |
Correct |
120 ms |
21924 KB |
Output is correct |
7 |
Correct |
64 ms |
17528 KB |
Output is correct |
8 |
Correct |
116 ms |
22204 KB |
Output is correct |
9 |
Correct |
75 ms |
22392 KB |
Output is correct |
10 |
Correct |
71 ms |
21880 KB |
Output is correct |
11 |
Correct |
74 ms |
23416 KB |
Output is correct |
12 |
Correct |
79 ms |
23544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
5 ms |
5376 KB |
Output is correct |
4 |
Correct |
5 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5248 KB |
Output is correct |
9 |
Correct |
5 ms |
5376 KB |
Output is correct |
10 |
Correct |
122 ms |
22520 KB |
Output is correct |
11 |
Correct |
119 ms |
23876 KB |
Output is correct |
12 |
Correct |
119 ms |
26360 KB |
Output is correct |
13 |
Correct |
136 ms |
25852 KB |
Output is correct |
14 |
Correct |
4 ms |
5248 KB |
Output is correct |
15 |
Correct |
120 ms |
21924 KB |
Output is correct |
16 |
Correct |
64 ms |
17528 KB |
Output is correct |
17 |
Correct |
116 ms |
22204 KB |
Output is correct |
18 |
Correct |
75 ms |
22392 KB |
Output is correct |
19 |
Correct |
71 ms |
21880 KB |
Output is correct |
20 |
Correct |
74 ms |
23416 KB |
Output is correct |
21 |
Correct |
79 ms |
23544 KB |
Output is correct |
22 |
Correct |
108 ms |
16120 KB |
Output is correct |
23 |
Correct |
89 ms |
14712 KB |
Output is correct |
24 |
Correct |
111 ms |
15480 KB |
Output is correct |
25 |
Correct |
4 ms |
5248 KB |
Output is correct |
26 |
Correct |
38 ms |
9720 KB |
Output is correct |
27 |
Correct |
91 ms |
14192 KB |
Output is correct |
28 |
Correct |
65 ms |
20216 KB |
Output is correct |
29 |
Correct |
74 ms |
23544 KB |
Output is correct |
30 |
Correct |
77 ms |
23160 KB |
Output is correct |
31 |
Correct |
5 ms |
5376 KB |
Output is correct |