/*
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] ];
}
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;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23892 KB |
Output is correct |
2 |
Correct |
14 ms |
24276 KB |
Output is correct |
3 |
Correct |
15 ms |
24332 KB |
Output is correct |
4 |
Correct |
15 ms |
24288 KB |
Output is correct |
5 |
Correct |
14 ms |
24336 KB |
Output is correct |
6 |
Correct |
13 ms |
23932 KB |
Output is correct |
7 |
Correct |
15 ms |
24020 KB |
Output is correct |
8 |
Correct |
14 ms |
24236 KB |
Output is correct |
9 |
Correct |
13 ms |
24276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
42012 KB |
Output is correct |
2 |
Correct |
81 ms |
43452 KB |
Output is correct |
3 |
Correct |
88 ms |
45356 KB |
Output is correct |
4 |
Correct |
112 ms |
45056 KB |
Output is correct |
5 |
Correct |
14 ms |
24020 KB |
Output is correct |
6 |
Correct |
84 ms |
41532 KB |
Output is correct |
7 |
Correct |
57 ms |
37024 KB |
Output is correct |
8 |
Correct |
81 ms |
41900 KB |
Output is correct |
9 |
Correct |
73 ms |
42612 KB |
Output is correct |
10 |
Correct |
74 ms |
42128 KB |
Output is correct |
11 |
Correct |
77 ms |
43556 KB |
Output is correct |
12 |
Correct |
74 ms |
43548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23892 KB |
Output is correct |
2 |
Correct |
14 ms |
24276 KB |
Output is correct |
3 |
Correct |
15 ms |
24332 KB |
Output is correct |
4 |
Correct |
15 ms |
24288 KB |
Output is correct |
5 |
Correct |
14 ms |
24336 KB |
Output is correct |
6 |
Correct |
13 ms |
23932 KB |
Output is correct |
7 |
Correct |
15 ms |
24020 KB |
Output is correct |
8 |
Correct |
14 ms |
24236 KB |
Output is correct |
9 |
Correct |
13 ms |
24276 KB |
Output is correct |
10 |
Correct |
80 ms |
42012 KB |
Output is correct |
11 |
Correct |
81 ms |
43452 KB |
Output is correct |
12 |
Correct |
88 ms |
45356 KB |
Output is correct |
13 |
Correct |
112 ms |
45056 KB |
Output is correct |
14 |
Correct |
14 ms |
24020 KB |
Output is correct |
15 |
Correct |
84 ms |
41532 KB |
Output is correct |
16 |
Correct |
57 ms |
37024 KB |
Output is correct |
17 |
Correct |
81 ms |
41900 KB |
Output is correct |
18 |
Correct |
73 ms |
42612 KB |
Output is correct |
19 |
Correct |
74 ms |
42128 KB |
Output is correct |
20 |
Correct |
77 ms |
43556 KB |
Output is correct |
21 |
Correct |
74 ms |
43548 KB |
Output is correct |
22 |
Correct |
102 ms |
41548 KB |
Output is correct |
23 |
Correct |
88 ms |
39464 KB |
Output is correct |
24 |
Correct |
100 ms |
41236 KB |
Output is correct |
25 |
Correct |
14 ms |
24136 KB |
Output is correct |
26 |
Correct |
58 ms |
31816 KB |
Output is correct |
27 |
Correct |
95 ms |
38800 KB |
Output is correct |
28 |
Correct |
61 ms |
42124 KB |
Output is correct |
29 |
Correct |
83 ms |
46092 KB |
Output is correct |
30 |
Correct |
77 ms |
45668 KB |
Output is correct |
31 |
Correct |
15 ms |
24208 KB |
Output is correct |