#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, K = 20;
long long n, a, b, c1, c2, ans, cnt[N], binlift[N][K], depth[N];
struct Edge{
long long b, c1, c2;
};
vector<Edge> tree[N];
void dfs(int v, int p){
binlift[v][0] = p;
for(int i = 1; i < K; i++) binlift[v][i] = binlift[binlift[v][i - 1]][i - 1];
depth[v] = depth[p] + 1;
for(auto e : tree[v]){
if(e.b != p){
dfs(e.b, v);
}
}
}
int lca(int a, int b){
if(depth[b] > depth[a]) swap(a, b);
for(int i = K - 1; i >= 0; i--) if(depth[binlift[a][i]] >= depth[b]) a = binlift[a][i];
if(a == b) return a;
for(int i = K - 1; i >= 0; i--){
if(binlift[a][i] != binlift[b][i]){
a = binlift[a][i], b = binlift[b][i];
}
}
return binlift[a][0];
}
void dfs2(int v, int p){
for(auto e : tree[v]){
if(e.b != p){
dfs2(e.b, v);
ans += min(e.c1 * cnt[e.b], e.c2);
cnt[v] += cnt[e.b];
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n - 1; i++){
cin >> a >> b >> c1 >> c2;
tree[a].push_back({b, c1, c2});
tree[b].push_back({a, c1, c2});
}
dfs(1, 0);
cnt[1]--, cnt[2]++;
for(int i = 2; i <= n - 1; i++){
int c = lca(i, i + 1);
cnt[c] -= 2;
cnt[i]++, cnt[i + 1]++;
}
dfs2(1, 0);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5460 KB |
Output is correct |
3 |
Correct |
5 ms |
5460 KB |
Output is correct |
4 |
Correct |
4 ms |
5460 KB |
Output is correct |
5 |
Correct |
5 ms |
5552 KB |
Output is correct |
6 |
Correct |
3 ms |
5040 KB |
Output is correct |
7 |
Correct |
3 ms |
5116 KB |
Output is correct |
8 |
Correct |
4 ms |
5332 KB |
Output is correct |
9 |
Correct |
4 ms |
5420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
32608 KB |
Output is correct |
2 |
Correct |
167 ms |
34124 KB |
Output is correct |
3 |
Correct |
206 ms |
37692 KB |
Output is correct |
4 |
Correct |
203 ms |
37280 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
162 ms |
31820 KB |
Output is correct |
7 |
Correct |
102 ms |
24632 KB |
Output is correct |
8 |
Correct |
174 ms |
32548 KB |
Output is correct |
9 |
Correct |
80 ms |
33928 KB |
Output is correct |
10 |
Correct |
78 ms |
33152 KB |
Output is correct |
11 |
Correct |
85 ms |
35444 KB |
Output is correct |
12 |
Correct |
90 ms |
35684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5460 KB |
Output is correct |
3 |
Correct |
5 ms |
5460 KB |
Output is correct |
4 |
Correct |
4 ms |
5460 KB |
Output is correct |
5 |
Correct |
5 ms |
5552 KB |
Output is correct |
6 |
Correct |
3 ms |
5040 KB |
Output is correct |
7 |
Correct |
3 ms |
5116 KB |
Output is correct |
8 |
Correct |
4 ms |
5332 KB |
Output is correct |
9 |
Correct |
4 ms |
5420 KB |
Output is correct |
10 |
Correct |
171 ms |
32608 KB |
Output is correct |
11 |
Correct |
167 ms |
34124 KB |
Output is correct |
12 |
Correct |
206 ms |
37692 KB |
Output is correct |
13 |
Correct |
203 ms |
37280 KB |
Output is correct |
14 |
Correct |
3 ms |
5204 KB |
Output is correct |
15 |
Correct |
162 ms |
31820 KB |
Output is correct |
16 |
Correct |
102 ms |
24632 KB |
Output is correct |
17 |
Correct |
174 ms |
32548 KB |
Output is correct |
18 |
Correct |
80 ms |
33928 KB |
Output is correct |
19 |
Correct |
78 ms |
33152 KB |
Output is correct |
20 |
Correct |
85 ms |
35444 KB |
Output is correct |
21 |
Correct |
90 ms |
35684 KB |
Output is correct |
22 |
Correct |
130 ms |
29988 KB |
Output is correct |
23 |
Correct |
109 ms |
26948 KB |
Output is correct |
24 |
Correct |
122 ms |
29536 KB |
Output is correct |
25 |
Correct |
3 ms |
5204 KB |
Output is correct |
26 |
Correct |
47 ms |
16216 KB |
Output is correct |
27 |
Correct |
106 ms |
26096 KB |
Output is correct |
28 |
Correct |
70 ms |
30472 KB |
Output is correct |
29 |
Correct |
89 ms |
35692 KB |
Output is correct |
30 |
Correct |
84 ms |
35264 KB |
Output is correct |
31 |
Correct |
4 ms |
5424 KB |
Output is correct |