#include <bits/stdc++.h>
using namespace std;
const int MXN = 200001;
const int lg = 20;
vector<array<int, 3>> adj[MXN];
struct LCA{
int up[lg][MXN];
int tin[MXN], tout[MXN];
int timer = 0;
LCA(){
dfs();
}
void dfs(int node = 0, int par = 0){
tin[node] = timer++;
up[0][node] = par;
for(int i = 1; i < lg; i++)
up[i][node] = up[i-1][up[i-1][node]];
for(auto& [v, c1, c2] : adj[node]){
if(v == par) continue;
dfs(v, node);
}
tout[node] = timer++;
}
bool isAncestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(isAncestor(u, v))
return u;
if(isAncestor(v, u))
return v;
for(int i = lg - 1; i >= 0; --i)
if(!isAncestor(up[i][u], v))
u = up[i][u];
return up[0][u];
}
};
int pref[MXN];
int64_t ans = 0;
void dfs(int node = 0, int par = -1){
for(auto& [v, c1, c2] : adj[node]){
if(v == par)
continue;
dfs(v, node);
pref[node] += pref[v];
ans += min(1LL*c1*pref[v], 1LL*c2);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 0; i < n-1; i++){
int u, v, c1, c2;
cin >> u >> v >> c1 >> c2;
--u, --v;
adj[u].push_back({v, c1, c2});
adj[v].push_back({u, c1, c2});
}
LCA Q;
for(int i = 1; i < n; i++){
int l = Q.lca(i, i-1);
if(l == i || l == i-1){
pref[l]--;
pref[l^(i-1)^i]++;
}
else{
pref[l] -= 2;
pref[i-1]++;
pref[i]++;
}
}
dfs();
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5356 KB |
Output is correct |
3 |
Correct |
5 ms |
5356 KB |
Output is correct |
4 |
Correct |
5 ms |
5356 KB |
Output is correct |
5 |
Correct |
6 ms |
5632 KB |
Output is correct |
6 |
Correct |
4 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5228 KB |
Output is correct |
8 |
Correct |
5 ms |
5356 KB |
Output is correct |
9 |
Correct |
5 ms |
5356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
19308 KB |
Output is correct |
2 |
Correct |
125 ms |
20372 KB |
Output is correct |
3 |
Correct |
146 ms |
21996 KB |
Output is correct |
4 |
Correct |
160 ms |
23920 KB |
Output is correct |
5 |
Correct |
4 ms |
5228 KB |
Output is correct |
6 |
Correct |
119 ms |
20716 KB |
Output is correct |
7 |
Correct |
72 ms |
16620 KB |
Output is correct |
8 |
Correct |
131 ms |
21156 KB |
Output is correct |
9 |
Correct |
76 ms |
21868 KB |
Output is correct |
10 |
Correct |
75 ms |
21356 KB |
Output is correct |
11 |
Correct |
80 ms |
22764 KB |
Output is correct |
12 |
Correct |
92 ms |
22892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5356 KB |
Output is correct |
3 |
Correct |
5 ms |
5356 KB |
Output is correct |
4 |
Correct |
5 ms |
5356 KB |
Output is correct |
5 |
Correct |
6 ms |
5632 KB |
Output is correct |
6 |
Correct |
4 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5228 KB |
Output is correct |
8 |
Correct |
5 ms |
5356 KB |
Output is correct |
9 |
Correct |
5 ms |
5356 KB |
Output is correct |
10 |
Correct |
126 ms |
19308 KB |
Output is correct |
11 |
Correct |
125 ms |
20372 KB |
Output is correct |
12 |
Correct |
146 ms |
21996 KB |
Output is correct |
13 |
Correct |
160 ms |
23920 KB |
Output is correct |
14 |
Correct |
4 ms |
5228 KB |
Output is correct |
15 |
Correct |
119 ms |
20716 KB |
Output is correct |
16 |
Correct |
72 ms |
16620 KB |
Output is correct |
17 |
Correct |
131 ms |
21156 KB |
Output is correct |
18 |
Correct |
76 ms |
21868 KB |
Output is correct |
19 |
Correct |
75 ms |
21356 KB |
Output is correct |
20 |
Correct |
80 ms |
22764 KB |
Output is correct |
21 |
Correct |
92 ms |
22892 KB |
Output is correct |
22 |
Correct |
137 ms |
20076 KB |
Output is correct |
23 |
Correct |
114 ms |
18284 KB |
Output is correct |
24 |
Correct |
131 ms |
19644 KB |
Output is correct |
25 |
Correct |
5 ms |
5376 KB |
Output is correct |
26 |
Correct |
57 ms |
11756 KB |
Output is correct |
27 |
Correct |
121 ms |
17772 KB |
Output is correct |
28 |
Correct |
68 ms |
19692 KB |
Output is correct |
29 |
Correct |
85 ms |
22892 KB |
Output is correct |
30 |
Correct |
83 ms |
22508 KB |
Output is correct |
31 |
Correct |
5 ms |
5356 KB |
Output is correct |