#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, Log = 20;
using ll = long long;
int n, a[N], b[N], c1[N], c2[N];
vector<tuple<int, int, int>> e[N];
ll ans;
int d[N];
int anc[N][Log];
int wc1[N], wc2[N];
int dep[N];
void dfs1(int u, int fa) {
anc[u][0] = fa;
dep[u] = dep[fa] + 1;
for (int i = 1; i < Log; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (auto ver: e[u]) {
int v, C1, C2;
tie(v, C1, C2) = ver;
if (v == fa) continue;
wc1[v] = C1;
wc2[v] = C2;
dfs1(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v])
swap(u, v);
for (int i = Log - 1; i >= 0; --i)
if (dep[anc[u][i]] >= dep[v])
u = anc[u][i];
if (u == v) return u;
for (int i = Log - 1; i >= 0; --i)
if (anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
return anc[u][0];
}
void dfs2(int u, int fa) {
for (auto ver: e[u]) {
int v = get<0>(ver);
if (v != fa)
dfs2(v, u), d[u] += d[v];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; ++i) {
scanf("%d%d%d%d", a+i, b+i, c1+i, c2+i);
e[a[i]].emplace_back(b[i], c1[i], c2[i]);
e[b[i]].emplace_back(a[i], c1[i], c2[i]);
}
dfs1(1, 0);
for (int i = 1; i <= n - 1; ++i) {
const int u = i, v = i + 1;
d[u] += 1, d[v] += 1, d[lca(u, v)] -= 2;
}
dfs2(1, 0);
for (int i = 2; i <= n; ++i)
ans += min((ll) wc2[i], 1ll * wc1[i] * d[i]);
cout << ans;
return 0;
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
putovanje.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d%d%d%d", a+i, b+i, c1+i, c2+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5016 KB |
Output is correct |
2 |
Correct |
4 ms |
5236 KB |
Output is correct |
3 |
Correct |
4 ms |
5332 KB |
Output is correct |
4 |
Correct |
5 ms |
5280 KB |
Output is correct |
5 |
Correct |
4 ms |
5276 KB |
Output is correct |
6 |
Correct |
3 ms |
5008 KB |
Output is correct |
7 |
Correct |
3 ms |
5152 KB |
Output is correct |
8 |
Correct |
4 ms |
5212 KB |
Output is correct |
9 |
Correct |
4 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
134 ms |
23488 KB |
Output is correct |
2 |
Correct |
136 ms |
24684 KB |
Output is correct |
3 |
Correct |
141 ms |
27268 KB |
Output is correct |
4 |
Correct |
156 ms |
26736 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
134 ms |
23120 KB |
Output is correct |
7 |
Correct |
78 ms |
18376 KB |
Output is correct |
8 |
Correct |
131 ms |
23500 KB |
Output is correct |
9 |
Correct |
78 ms |
24192 KB |
Output is correct |
10 |
Correct |
74 ms |
23764 KB |
Output is correct |
11 |
Correct |
86 ms |
25304 KB |
Output is correct |
12 |
Correct |
87 ms |
25512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5016 KB |
Output is correct |
2 |
Correct |
4 ms |
5236 KB |
Output is correct |
3 |
Correct |
4 ms |
5332 KB |
Output is correct |
4 |
Correct |
5 ms |
5280 KB |
Output is correct |
5 |
Correct |
4 ms |
5276 KB |
Output is correct |
6 |
Correct |
3 ms |
5008 KB |
Output is correct |
7 |
Correct |
3 ms |
5152 KB |
Output is correct |
8 |
Correct |
4 ms |
5212 KB |
Output is correct |
9 |
Correct |
4 ms |
5332 KB |
Output is correct |
10 |
Correct |
134 ms |
23488 KB |
Output is correct |
11 |
Correct |
136 ms |
24684 KB |
Output is correct |
12 |
Correct |
141 ms |
27268 KB |
Output is correct |
13 |
Correct |
156 ms |
26736 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
134 ms |
23120 KB |
Output is correct |
16 |
Correct |
78 ms |
18376 KB |
Output is correct |
17 |
Correct |
131 ms |
23500 KB |
Output is correct |
18 |
Correct |
78 ms |
24192 KB |
Output is correct |
19 |
Correct |
74 ms |
23764 KB |
Output is correct |
20 |
Correct |
86 ms |
25304 KB |
Output is correct |
21 |
Correct |
87 ms |
25512 KB |
Output is correct |
22 |
Correct |
116 ms |
21788 KB |
Output is correct |
23 |
Correct |
101 ms |
19648 KB |
Output is correct |
24 |
Correct |
104 ms |
21324 KB |
Output is correct |
25 |
Correct |
3 ms |
5204 KB |
Output is correct |
26 |
Correct |
43 ms |
12448 KB |
Output is correct |
27 |
Correct |
114 ms |
19096 KB |
Output is correct |
28 |
Correct |
69 ms |
21912 KB |
Output is correct |
29 |
Correct |
88 ms |
25488 KB |
Output is correct |
30 |
Correct |
79 ms |
25152 KB |
Output is correct |
31 |
Correct |
4 ms |
5204 KB |
Output is correct |