#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5;
int n, c1[mxN], c2[mxN], dep[mxN], anc[mxN][18];
vector<ar<int, 3>> adj[mxN];
void dfs1(int u=0, int p=-1) {
for (int i=1; i<18; ++i) anc[u][i]=anc[anc[u][i-1]][i-1];
for (auto& v : adj[u]) if (v[0]!=p) {
c1[v[0]]=v[1];
c2[v[0]]=v[2];
dep[v[0]]=dep[u]+1;
anc[v[0]][0]=u;
dfs1(v[0], u);
}
}
int lca(int a, int b) {
if (dep[a]>dep[b]) swap(a, b);
for (int i=17; ~i; --i) if (dep[b]-(1<<i)>=dep[a]) b=anc[b][i];
if (a==b) return a;
for (int i=17; ~i; --i) if (anc[a][i]!=anc[b][i]) a=anc[a][i], b=anc[b][i];
return anc[a][0];
}
int cnt[mxN];
void dfs2(int u=0, int p=-1) {
for (auto& v : adj[u]) if (v[0]!=p) {
dfs2(v[0], u);
cnt[u]+=cnt[v[0]];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=1; i<n; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d, --a, --b;
adj[a].push_back({b, c, d});
adj[b].push_back({a, c, d});
}
dfs1();
for (int i=1; i<n; ++i) {
++cnt[i], ++cnt[i-1];
cnt[lca(i, i-1)]-=2;
}
dfs2();
ll ans=0;
for (int i=1; i<n; ++i) ans+=min((ll)cnt[i]*c1[i], (ll)c2[i]);
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
5 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5368 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 |
154 ms |
19836 KB |
Output is correct |
2 |
Correct |
157 ms |
20472 KB |
Output is correct |
3 |
Correct |
173 ms |
22136 KB |
Output is correct |
4 |
Correct |
182 ms |
22008 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
159 ms |
19352 KB |
Output is correct |
7 |
Correct |
85 ms |
15480 KB |
Output is correct |
8 |
Correct |
152 ms |
19792 KB |
Output is correct |
9 |
Correct |
80 ms |
20344 KB |
Output is correct |
10 |
Correct |
79 ms |
19948 KB |
Output is correct |
11 |
Correct |
82 ms |
20984 KB |
Output is correct |
12 |
Correct |
90 ms |
20984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
5 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5368 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 |
154 ms |
19836 KB |
Output is correct |
11 |
Correct |
157 ms |
20472 KB |
Output is correct |
12 |
Correct |
173 ms |
22136 KB |
Output is correct |
13 |
Correct |
182 ms |
22008 KB |
Output is correct |
14 |
Correct |
4 ms |
5120 KB |
Output is correct |
15 |
Correct |
159 ms |
19352 KB |
Output is correct |
16 |
Correct |
85 ms |
15480 KB |
Output is correct |
17 |
Correct |
152 ms |
19792 KB |
Output is correct |
18 |
Correct |
80 ms |
20344 KB |
Output is correct |
19 |
Correct |
79 ms |
19948 KB |
Output is correct |
20 |
Correct |
82 ms |
20984 KB |
Output is correct |
21 |
Correct |
90 ms |
20984 KB |
Output is correct |
22 |
Correct |
126 ms |
19284 KB |
Output is correct |
23 |
Correct |
112 ms |
17784 KB |
Output is correct |
24 |
Correct |
130 ms |
19192 KB |
Output is correct |
25 |
Correct |
5 ms |
5248 KB |
Output is correct |
26 |
Correct |
46 ms |
11384 KB |
Output is correct |
27 |
Correct |
104 ms |
17272 KB |
Output is correct |
28 |
Correct |
74 ms |
18680 KB |
Output is correct |
29 |
Correct |
91 ms |
20984 KB |
Output is correct |
30 |
Correct |
85 ms |
21112 KB |
Output is correct |
31 |
Correct |
5 ms |
5248 KB |
Output is correct |