#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
const int MX_N = 2e5+5;
int N;
vector<tuple<int,int,int>> al[MX_N];
struct FenwickTree {
vector<int> ft;
int n;
void init(int _n) {
n = _n;
ft.assign(n+1,0);
}
void u(int i, int x) { for (; i <= n; i += i&-i) ft[i] += x; }
int query(int i) { int sum = 0; for (; i; i -= i&-i) sum += ft[i]; return sum; }
void update(int i, int j, int x) { u(i,x); u(j+1,-x); }
} ft;
pair<int,int> weight[MX_N];
/* custom ds of you choice */
int cnt = 1;
int pa[MX_N], dep[MX_N];
int heavy[MX_N], head[MX_N], pos[MX_N];
// heavy stores the heavy child of this vertex
// head stores the head/top of the chain this vertex is in
// pos relabels vertices to work with custom ds of your choice
int dfs(int u, int p, int d) {
pa[u] = p;
dep[u] = d;
heavy[u] = -1;
int sz = 1, mchild = 0;
for (auto e : al[u]) {
int v = get<0>(e);
if (v == p) continue;
weight[v] = make_pair(get<1>(e),get<2>(e));
int cs = dfs(v, u, d+1);
sz += cs;
if (cs > mchild) {
mchild = cs;
heavy[u] = v;
}
}
return sz;
}
void hld(int u, int p, int h) {
head[u] = h;
pos[u] = cnt++;
if (heavy[u] != -1) hld(heavy[u], u, h);
for (auto e : al[u]) {
int v = get<0>(e);
if (v == p) continue;
if (v != p and v != heavy[u]) {
hld(v, u, v);
}
}
}
void update_path(int a, int b, int v) {
for (; head[a] != head[b]; a = pa[head[a]]) { // go up the chains
if (dep[head[a]] < dep[head[b]]) swap(a, b);
ft.update(pos[head[a]], pos[a], v); // update the entire chain
}
if (a == b) return;
if (dep[a] < dep[b]) swap(a, b);
ft.update(pos[b]+1, pos[a], v); // update part of the chain required
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
FOR(i,1,N-1){
int A, B, C, D; cin >> A >> B >> C >> D;
al[A].emplace_back(B,C,D);
al[B].emplace_back(A,C,D);
}
dfs(1,0,0);
hld(1,0,1);
ft.init(N);
FOR(i,1,N-1){
update_path(i,i+1,1);
}
long long ans = 0;
FOR(i,2,N){
//cout << i << " :: " << ft.query(pos[i]) << endl;
ans += min(1LL * weight[i].first * ft.query(pos[i]), (long long)weight[i].second);
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
9 ms |
5248 KB |
Output is correct |
3 |
Correct |
10 ms |
5248 KB |
Output is correct |
4 |
Correct |
9 ms |
5248 KB |
Output is correct |
5 |
Correct |
9 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
10 ms |
5248 KB |
Output is correct |
9 |
Correct |
9 ms |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
14968 KB |
Output is correct |
2 |
Correct |
81 ms |
16164 KB |
Output is correct |
3 |
Correct |
90 ms |
17528 KB |
Output is correct |
4 |
Correct |
94 ms |
16760 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
84 ms |
14712 KB |
Output is correct |
7 |
Correct |
57 ms |
12536 KB |
Output is correct |
8 |
Correct |
81 ms |
16632 KB |
Output is correct |
9 |
Correct |
73 ms |
16888 KB |
Output is correct |
10 |
Correct |
76 ms |
16556 KB |
Output is correct |
11 |
Correct |
81 ms |
17528 KB |
Output is correct |
12 |
Correct |
85 ms |
17784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
9 ms |
5248 KB |
Output is correct |
3 |
Correct |
10 ms |
5248 KB |
Output is correct |
4 |
Correct |
9 ms |
5248 KB |
Output is correct |
5 |
Correct |
9 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
10 ms |
5248 KB |
Output is correct |
9 |
Correct |
9 ms |
5248 KB |
Output is correct |
10 |
Correct |
79 ms |
14968 KB |
Output is correct |
11 |
Correct |
81 ms |
16164 KB |
Output is correct |
12 |
Correct |
90 ms |
17528 KB |
Output is correct |
13 |
Correct |
94 ms |
16760 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
84 ms |
14712 KB |
Output is correct |
16 |
Correct |
57 ms |
12536 KB |
Output is correct |
17 |
Correct |
81 ms |
16632 KB |
Output is correct |
18 |
Correct |
73 ms |
16888 KB |
Output is correct |
19 |
Correct |
76 ms |
16556 KB |
Output is correct |
20 |
Correct |
81 ms |
17528 KB |
Output is correct |
21 |
Correct |
85 ms |
17784 KB |
Output is correct |
22 |
Correct |
142 ms |
14304 KB |
Output is correct |
23 |
Correct |
123 ms |
13176 KB |
Output is correct |
24 |
Correct |
147 ms |
14076 KB |
Output is correct |
25 |
Correct |
10 ms |
5120 KB |
Output is correct |
26 |
Correct |
61 ms |
9080 KB |
Output is correct |
27 |
Correct |
120 ms |
12944 KB |
Output is correct |
28 |
Correct |
64 ms |
15352 KB |
Output is correct |
29 |
Correct |
81 ms |
17784 KB |
Output is correct |
30 |
Correct |
79 ms |
17400 KB |
Output is correct |
31 |
Correct |
8 ms |
5248 KB |
Output is correct |