#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class F> struct RecLambda : private F {
explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
vector<int> to(2 * N - 2), once(2 * N - 2), mult(2 * N - 2);
vector<vector<int>> graph(N);
for (int i = 0; i < N - 1; ++i) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
a -= 1, b -= 1;
to[2 * i] = b;
to[2 * i + 1] = a;
once[2 * i] = once[2 * i + 1] = c;
mult[2 * i] = mult[2 * i + 1] = d;
graph[a].push_back(2 * i);
graph[b].push_back(2 * i + 1);
}
vector<int> depth(N);
array<vector<int>, 20> parent;
parent[0] = vector(N, 0);
RecLambda([&](auto&& dfs, const int u, const int p) -> void {
parent[0][u] = p;
for (const int e : graph[u]) {
if (to[e] != p) {
depth[to[e]] = depth[u] + 1;
dfs(to[e], u);
}
}
})(0, 0);
for (int k = 0; k < 19; ++k) {
parent[k + 1] = vector(N, 0);
for (int i = 0; i < N; ++i) {
parent[k + 1][i] = parent[k][parent[k][i]];
}
}
const auto lca = [&](int u, int v) {
if (depth[u] < depth[v]) {
std::swap(u, v);
}
for (int dif = depth[u] - depth[v], k = 0; k < 20; ++k) {
if (dif >> k & 1) {
u = parent[k][u];
}
}
if (u == v) {
return u;
}
for (int k = 19; k >= 0; --k) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
};
vector<int> coeff(N);
for (int i = 1; i < N; ++i) {
const int j = lca(i - 1, i);
coeff[i - 1] += 1;
coeff[i] += 1;
coeff[j] -= 2;
}
long long ans = 0;
RecLambda([&](auto&& dfs, const int u, const int p) -> void {
for (const int e : graph[u]) {
if (to[e] != p) {
dfs(to[e], u);
coeff[u] += coeff[to[e]];
ans += std::min((long long)coeff[to[e]] * once[e], (long long)mult[e]);
}
}
})(0, 0);
std::cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
588 KB |
Output is correct |
4 |
Correct |
2 ms |
584 KB |
Output is correct |
5 |
Correct |
2 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
19520 KB |
Output is correct |
2 |
Correct |
74 ms |
20432 KB |
Output is correct |
3 |
Correct |
91 ms |
22988 KB |
Output is correct |
4 |
Correct |
93 ms |
22728 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
81 ms |
19032 KB |
Output is correct |
7 |
Correct |
48 ms |
13820 KB |
Output is correct |
8 |
Correct |
84 ms |
19516 KB |
Output is correct |
9 |
Correct |
58 ms |
20684 KB |
Output is correct |
10 |
Correct |
54 ms |
20040 KB |
Output is correct |
11 |
Correct |
62 ms |
21688 KB |
Output is correct |
12 |
Correct |
66 ms |
21960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
588 KB |
Output is correct |
4 |
Correct |
2 ms |
584 KB |
Output is correct |
5 |
Correct |
2 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
85 ms |
19520 KB |
Output is correct |
11 |
Correct |
74 ms |
20432 KB |
Output is correct |
12 |
Correct |
91 ms |
22988 KB |
Output is correct |
13 |
Correct |
93 ms |
22728 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
81 ms |
19032 KB |
Output is correct |
16 |
Correct |
48 ms |
13820 KB |
Output is correct |
17 |
Correct |
84 ms |
19516 KB |
Output is correct |
18 |
Correct |
58 ms |
20684 KB |
Output is correct |
19 |
Correct |
54 ms |
20040 KB |
Output is correct |
20 |
Correct |
62 ms |
21688 KB |
Output is correct |
21 |
Correct |
66 ms |
21960 KB |
Output is correct |
22 |
Correct |
103 ms |
18376 KB |
Output is correct |
23 |
Correct |
94 ms |
16256 KB |
Output is correct |
24 |
Correct |
110 ms |
17988 KB |
Output is correct |
25 |
Correct |
1 ms |
460 KB |
Output is correct |
26 |
Correct |
41 ms |
8344 KB |
Output is correct |
27 |
Correct |
78 ms |
15560 KB |
Output is correct |
28 |
Correct |
51 ms |
18116 KB |
Output is correct |
29 |
Correct |
81 ms |
22044 KB |
Output is correct |
30 |
Correct |
58 ms |
21584 KB |
Output is correct |
31 |
Correct |
1 ms |
588 KB |
Output is correct |