#include <bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
struct Edge {
int v, c1, c2;
};
class LowestCommonAncestor {
private:
struct Node {
int depth, label;
Node *parent, *jump;
Node() {}
Node(Node *p) {
parent = p;
depth = p->depth + 1;
if (p->depth - p->jump->depth
== p->jump->depth - p->jump->jump->depth) {
jump = p->jump->jump;
}
else jump = p;
}
};
int n;
vector<Node*> t;
vector<vector<int>> adj;
public:
LowestCommonAncestor(int n): n(n), t(n + 1), adj(n + 1) {}
void add_edge(int u, int v) {
adj[u].push_back(v);
}
void build() {
t[1] = new Node();
t[1]->depth = 0;
t[1]->jump = t[1];
t[1]->parent = nullptr;
t[1]->label = 1;
dfs(1, 1);
}
void dfs(int u, int p) {
for (int v: adj[u]) if (v != p) {
t[v] = new Node(t[u]);
t[v]->label = v;
dfs(v, u);
}
}
int find(int u, int d) {
Node *pu = t[u];
while (pu->depth > d) {
if (pu->jump->depth < d)
pu = pu->parent;
else
pu = pu->jump;
}
return pu->label;
}
int get(int u, int v) {
if (t[u]->depth < t[v]->depth) swap(u, v);
u = find(u, t[v]->depth);
Node *pu = t[u], *pv = t[v];
while (pu != pv) {
if (pu->jump == pv->jump) {
pu = pu->parent;
pv = pv->parent;
}
else {
pu = pu->jump;
pv = pv->jump;
}
}
return pu->label;
}
};
void Input() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
}
void Solve() {
int n; cin >> n;
vector<vector<Edge>> adj(n + 1);
LowestCommonAncestor lca(n);
for (int i = 1; i < n; i++) {
int u, v, c1, c2;
cin >> u >> v >> c1 >> c2;
lca.add_edge(u, v);
lca.add_edge(v, u);
adj[u].push_back({v, c1, c2});
adj[v].push_back({u, c1, c2});
}
lca.build();
vector<ll> freq(n + 1, 0);
for (int i = 2; i <= n; i++) {
int l = lca.get(i - 1, i);
freq[i - 1]++;
freq[i]++;
freq[l] -= 2;
}
ll ans = 0;
function<void(int, int)> dfs = [&](int u, int p) {
for (Edge &e: adj[u])
if (e.v != p) {
dfs(e.v, u);
ans += min(freq[e.v] * e.c1, e.c2 * 1ll);
freq[u] += freq[e.v];
}
};
dfs(1, 1);
cout << ans;
}
int main(){
clock_t begin = clock();
Input();
Solve();
cerr << "Time: " << (clock() - begin + 1.0) / CLOCKS_PER_SEC << "s";
return 0;
}
Compilation message
putovanje.cpp: In function 'void Input()':
putovanje.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
696 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
21072 KB |
Output is correct |
2 |
Correct |
75 ms |
22568 KB |
Output is correct |
3 |
Correct |
74 ms |
25528 KB |
Output is correct |
4 |
Correct |
80 ms |
24656 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
68 ms |
20556 KB |
Output is correct |
7 |
Correct |
42 ms |
15440 KB |
Output is correct |
8 |
Correct |
70 ms |
21076 KB |
Output is correct |
9 |
Correct |
51 ms |
21844 KB |
Output is correct |
10 |
Correct |
51 ms |
21336 KB |
Output is correct |
11 |
Correct |
58 ms |
23156 KB |
Output is correct |
12 |
Correct |
53 ms |
23196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
696 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
66 ms |
21072 KB |
Output is correct |
11 |
Correct |
75 ms |
22568 KB |
Output is correct |
12 |
Correct |
74 ms |
25528 KB |
Output is correct |
13 |
Correct |
80 ms |
24656 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
68 ms |
20556 KB |
Output is correct |
16 |
Correct |
42 ms |
15440 KB |
Output is correct |
17 |
Correct |
70 ms |
21076 KB |
Output is correct |
18 |
Correct |
51 ms |
21844 KB |
Output is correct |
19 |
Correct |
51 ms |
21336 KB |
Output is correct |
20 |
Correct |
58 ms |
23156 KB |
Output is correct |
21 |
Correct |
53 ms |
23196 KB |
Output is correct |
22 |
Correct |
63 ms |
18652 KB |
Output is correct |
23 |
Correct |
61 ms |
16468 KB |
Output is correct |
24 |
Correct |
62 ms |
18260 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
24 ms |
8416 KB |
Output is correct |
27 |
Correct |
49 ms |
15956 KB |
Output is correct |
28 |
Correct |
43 ms |
19248 KB |
Output is correct |
29 |
Correct |
53 ms |
23096 KB |
Output is correct |
30 |
Correct |
54 ms |
22752 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |