#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define debug(x) cout << #x << ": " << (x) << endl
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int mxN = 2e5+5;
const int mxM = 2e5+5;
const int logN = 20;
vector<pair<int, int>> g[mxN];
int tin[mxN];
int tout[mxN];
int up[mxN][logN];
int dfstime = 0;
void dfs(int a, int p)
{
tin[a] = dfstime++;
up[a][0] = p;
for (int j = 1; j < logN; j++) {
up[a][j] = up[ up[a][j-1] ][j-1];
}
for (auto [b, idx]: g[a]) {
if (b == p) continue;
dfs(b, a);
}
tout[a] = dfstime;
}
bool is_ancestor(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int psum[mxN];
int get_lca(int a, int b)
{
if (is_ancestor(a, b)) {
return a;
}
if (is_ancestor(b, a)) {
return b;
}
for (int j = logN -1; j >= 0; j--) {
if (!is_ancestor(up[a][j], b)) {
a = up[a][j];
}
}
return up[a][0];
}
int single[mxM];
int multi[mxM];
int used[mxM];
int dfs2(int a, int p) {
int ans = 0;
for (auto [b, idx]: g[a]) {
if (b == p) continue;
int t = dfs2(b, a);
used[idx] = t;
ans += t;
}
return ans + psum[a];
}
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b, s, m;
cin >> a >> b >> s >> m;
a--; b--;
single[i] = s;
multi[i] = m;
g[a].pb({b, i});
g[b].pb({a, i});
}
dfs(0, 0);
for (int a = 0; a < n-1; a++) {
int b = a + 1;
int lca = get_lca(a, b);
psum[a]++;
psum[b]++;
psum[lca] -= 2;
}
dfs2(0, 0);
int ans = 0;
for (int i = 0; i < n-1; i++) {
ans += min(multi[i], used[i]*single[i]);
}
cout << ans << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5536 KB |
Output is correct |
3 |
Correct |
3 ms |
5588 KB |
Output is correct |
4 |
Correct |
4 ms |
5488 KB |
Output is correct |
5 |
Correct |
3 ms |
5560 KB |
Output is correct |
6 |
Correct |
2 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
5204 KB |
Output is correct |
8 |
Correct |
3 ms |
5332 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
32120 KB |
Output is correct |
2 |
Correct |
78 ms |
33300 KB |
Output is correct |
3 |
Correct |
98 ms |
36424 KB |
Output is correct |
4 |
Correct |
114 ms |
36604 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
107 ms |
31564 KB |
Output is correct |
7 |
Correct |
46 ms |
24112 KB |
Output is correct |
8 |
Correct |
89 ms |
32356 KB |
Output is correct |
9 |
Correct |
66 ms |
33936 KB |
Output is correct |
10 |
Correct |
62 ms |
33172 KB |
Output is correct |
11 |
Correct |
73 ms |
35536 KB |
Output is correct |
12 |
Correct |
67 ms |
35660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5536 KB |
Output is correct |
3 |
Correct |
3 ms |
5588 KB |
Output is correct |
4 |
Correct |
4 ms |
5488 KB |
Output is correct |
5 |
Correct |
3 ms |
5560 KB |
Output is correct |
6 |
Correct |
2 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
5204 KB |
Output is correct |
8 |
Correct |
3 ms |
5332 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
83 ms |
32120 KB |
Output is correct |
11 |
Correct |
78 ms |
33300 KB |
Output is correct |
12 |
Correct |
98 ms |
36424 KB |
Output is correct |
13 |
Correct |
114 ms |
36604 KB |
Output is correct |
14 |
Correct |
3 ms |
5204 KB |
Output is correct |
15 |
Correct |
107 ms |
31564 KB |
Output is correct |
16 |
Correct |
46 ms |
24112 KB |
Output is correct |
17 |
Correct |
89 ms |
32356 KB |
Output is correct |
18 |
Correct |
66 ms |
33936 KB |
Output is correct |
19 |
Correct |
62 ms |
33172 KB |
Output is correct |
20 |
Correct |
73 ms |
35536 KB |
Output is correct |
21 |
Correct |
67 ms |
35660 KB |
Output is correct |
22 |
Correct |
104 ms |
31652 KB |
Output is correct |
23 |
Correct |
76 ms |
28492 KB |
Output is correct |
24 |
Correct |
86 ms |
31136 KB |
Output is correct |
25 |
Correct |
3 ms |
5332 KB |
Output is correct |
26 |
Correct |
35 ms |
17052 KB |
Output is correct |
27 |
Correct |
97 ms |
27472 KB |
Output is correct |
28 |
Correct |
58 ms |
30540 KB |
Output is correct |
29 |
Correct |
77 ms |
35672 KB |
Output is correct |
30 |
Correct |
67 ms |
35236 KB |
Output is correct |
31 |
Correct |
3 ms |
5460 KB |
Output is correct |