#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
const int mxn = 200000;
int n;
ll u[mxn], v[mxn], w[mxn], z[mxn];
int vis[mxn], par[mxn], rnk[mxn], p[mxn], dp[mxn];
vector<int> g[mxn];
int fnd(int x){
return x == par[x] ? x : par[x] = fnd(par[x]);
}
ll dfs(int c){
ll ret = 0;
vis[c] = 1, p[c] = par[c] = c, dp[c] = 1 + (c && c < n - 1);
for(int i = c - 1; i <= c + 1; i += 2){
if(i >= 0 && i < n && vis[i]) dp[p[fnd(i)]] -= 2;
}
for(int i : g[c]) if(!vis[c ^ u[i] ^ v[i]]){
if(u[i] != c) swap(u[i], v[i]);
ret += dfs(v[i]);
dp[c] += dp[v[i]];
ret += min(w[i] * dp[v[i]], z[i]);
int x = fnd(c), y = fnd(v[i]);
if(rnk[x] < rnk[y]) swap(x, y);
rnk[x] += rnk[x] == rnk[y];
par[y] = x, p[x] = c;
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n - 1; i++){
cin >> u[i] >> v[i] >> w[i] >> z[i];
g[--u[i]].push_back(i);
g[--v[i]].push_back(i);
}
cout << dfs(0) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
5 ms |
5248 KB |
Output is correct |
4 |
Correct |
5 ms |
5248 KB |
Output is correct |
5 |
Correct |
5 ms |
5248 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 |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
15480 KB |
Output is correct |
2 |
Correct |
69 ms |
16376 KB |
Output is correct |
3 |
Correct |
79 ms |
17784 KB |
Output is correct |
4 |
Correct |
94 ms |
17400 KB |
Output is correct |
5 |
Correct |
5 ms |
5120 KB |
Output is correct |
6 |
Correct |
81 ms |
15352 KB |
Output is correct |
7 |
Correct |
45 ms |
12924 KB |
Output is correct |
8 |
Correct |
71 ms |
15480 KB |
Output is correct |
9 |
Correct |
55 ms |
15736 KB |
Output is correct |
10 |
Correct |
54 ms |
15352 KB |
Output is correct |
11 |
Correct |
60 ms |
16120 KB |
Output is correct |
12 |
Correct |
65 ms |
16120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
5248 KB |
Output is correct |
3 |
Correct |
5 ms |
5248 KB |
Output is correct |
4 |
Correct |
5 ms |
5248 KB |
Output is correct |
5 |
Correct |
5 ms |
5248 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 |
5248 KB |
Output is correct |
10 |
Correct |
72 ms |
15480 KB |
Output is correct |
11 |
Correct |
69 ms |
16376 KB |
Output is correct |
12 |
Correct |
79 ms |
17784 KB |
Output is correct |
13 |
Correct |
94 ms |
17400 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
81 ms |
15352 KB |
Output is correct |
16 |
Correct |
45 ms |
12924 KB |
Output is correct |
17 |
Correct |
71 ms |
15480 KB |
Output is correct |
18 |
Correct |
55 ms |
15736 KB |
Output is correct |
19 |
Correct |
54 ms |
15352 KB |
Output is correct |
20 |
Correct |
60 ms |
16120 KB |
Output is correct |
21 |
Correct |
65 ms |
16120 KB |
Output is correct |
22 |
Correct |
92 ms |
13176 KB |
Output is correct |
23 |
Correct |
84 ms |
12280 KB |
Output is correct |
24 |
Correct |
98 ms |
13176 KB |
Output is correct |
25 |
Correct |
4 ms |
5248 KB |
Output is correct |
26 |
Correct |
36 ms |
8952 KB |
Output is correct |
27 |
Correct |
83 ms |
12024 KB |
Output is correct |
28 |
Correct |
50 ms |
14456 KB |
Output is correct |
29 |
Correct |
61 ms |
16120 KB |
Output is correct |
30 |
Correct |
59 ms |
16120 KB |
Output is correct |
31 |
Correct |
5 ms |
5248 KB |
Output is correct |