#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
int n;
vector<pair<int, ii>> adj[200000];
int pa[200000][20];
int depth[200000];
int in[200000], out[200000], ctr = 0;
void dfs(int u, int p, int d) {
in[u] = ctr++;
pa[u][0] = p;
depth[u] = d;
for (auto v : adj[u]) {
if (v.f != p) dfs(v.f, u, d+1);
}
out[u] = ctr-1;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int i = 19; i >= 0; i--) {
if (depth[pa[a][i]] >= depth[b]) a = pa[a][i];
}
if (a == b) return a;
for (int i = 19; i >= 0; i--) {
if (pa[a][i] != pa[b][i]) {
a = pa[a][i], b = pa[b][i];
}
}
return pa[a][0];
}
int ft[200001];
void upd(int k, int v) {
k++;
while (k <= 200000) {
ft[k] += v;
k += k&-k;
}
}
int qry(int k) {
k++;
int ans = 0;
while(k) {
ans += ft[k];
k -= k&-k;
}
return ans;
}
ll ans = 0;
void dfs2(int u, int p) {
for (auto v : adj[u]) {
if (v.f == p) continue;
assert(depth[v.f] = depth[u]+1);
ll numTraversals = qry(out[v.f]) - qry(in[v.f]-1);
//cout << u << "->" << v.f << ": " << min(numTraversals*v.s.f, (ll)v.s.s) << endl;
ans += min(numTraversals*v.s.f, (ll)v.s.s);
dfs2(v.f, u);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b, c, d; cin >> a >> b >> c >> d; --a; --b;
adj[a].push_back(mp(b, mp(c, d)));
adj[b].push_back(mp(a, mp(c, d)));
}
dfs(0, 0, 0);
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
pa[i][j] = pa[pa[i][j-1]][j-1];
}
}
for (int i = 0; i < n-1; i++) {
int x = lca(i, i+1);
assert(depth[i] >= depth[x]);
assert(depth[i+1] >= depth[x]);
upd(in[i], 1);
upd(in[i+1], 1);
upd(in[x], -2);
}
dfs2(0, 0);
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5376 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
6 ms |
5376 KB |
Output is correct |
5 |
Correct |
6 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 |
182 ms |
19608 KB |
Output is correct |
2 |
Correct |
195 ms |
20600 KB |
Output is correct |
3 |
Correct |
201 ms |
22264 KB |
Output is correct |
4 |
Correct |
221 ms |
22136 KB |
Output is correct |
5 |
Correct |
4 ms |
5248 KB |
Output is correct |
6 |
Correct |
178 ms |
19192 KB |
Output is correct |
7 |
Correct |
107 ms |
15480 KB |
Output is correct |
8 |
Correct |
194 ms |
21372 KB |
Output is correct |
9 |
Correct |
110 ms |
22136 KB |
Output is correct |
10 |
Correct |
103 ms |
21624 KB |
Output is correct |
11 |
Correct |
111 ms |
23032 KB |
Output is correct |
12 |
Correct |
116 ms |
23288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5376 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
6 ms |
5376 KB |
Output is correct |
5 |
Correct |
6 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 |
182 ms |
19608 KB |
Output is correct |
11 |
Correct |
195 ms |
20600 KB |
Output is correct |
12 |
Correct |
201 ms |
22264 KB |
Output is correct |
13 |
Correct |
221 ms |
22136 KB |
Output is correct |
14 |
Correct |
4 ms |
5248 KB |
Output is correct |
15 |
Correct |
178 ms |
19192 KB |
Output is correct |
16 |
Correct |
107 ms |
15480 KB |
Output is correct |
17 |
Correct |
194 ms |
21372 KB |
Output is correct |
18 |
Correct |
110 ms |
22136 KB |
Output is correct |
19 |
Correct |
103 ms |
21624 KB |
Output is correct |
20 |
Correct |
111 ms |
23032 KB |
Output is correct |
21 |
Correct |
116 ms |
23288 KB |
Output is correct |
22 |
Correct |
166 ms |
20344 KB |
Output is correct |
23 |
Correct |
142 ms |
18552 KB |
Output is correct |
24 |
Correct |
158 ms |
19964 KB |
Output is correct |
25 |
Correct |
5 ms |
5248 KB |
Output is correct |
26 |
Correct |
60 ms |
11876 KB |
Output is correct |
27 |
Correct |
125 ms |
17920 KB |
Output is correct |
28 |
Correct |
93 ms |
19960 KB |
Output is correct |
29 |
Correct |
116 ms |
23272 KB |
Output is correct |
30 |
Correct |
109 ms |
22904 KB |
Output is correct |
31 |
Correct |
6 ms |
5376 KB |
Output is correct |