/******************************
* author : @marvinthang *
* date : 14 / 11 / 2021 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false);\
cin.tie(NULL);\
//cout.tie(NULL);
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
const int MOD = 1e9 + 7; // 998244353;
const double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const long long oo = 1e18;
const int MAX = 2e5 + 5;
const int LOG = 18;
struct EDGE {
int u, v, cost1, costfull;
bool operator < (const EDGE &a) const {
return u == a.u ? v < a.v : u < a.u;
}
};
int numNode;
EDGE edges[MAX];
vector <int> adj[MAX];
int par[MAX], pref[MAX], anc[MAX][LOG], depth[MAX];
int findEdge(int u, int v) {
if (u > v) swap(u, v);
EDGE tmp = {u, v, 0, 0};
int l = 1, r = numNode - 1, res = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (edges[mid].u == u && edges[mid].v == v) return mid;
if (edges[mid] < tmp) l = mid + 1;
else r = mid - 1;
}
return res;
}
void dfs(int u) {
depth[u] = depth[anc[u][0]] + 1;
for (int i = 1; i < LOG; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (auto &v: adj[u]) {
if (v == anc[u][0]) continue;
int id = findEdge(u, v);
par[v] = id;
anc[v][0] = u;
dfs(v);
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; --i) {
if (depth[anc[u][i]] >= depth[v]) u = anc[u][i];
}
if (u == v) return u;
for (int i = LOG - 1; i >= 0; --i) {
if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
void dfs2(int u) {
for (auto &v: adj[u]) {
if (v == anc[u][0]) continue;
dfs2(v);
pref[par[u]] += pref[par[v]];
}
}
int main() {
superspeed;
#ifndef ONLINE_JUDGE
file("BEER");
#endif
cin >> numNode;
for (int i = 1; i < numNode; ++i) {
int u, v, c1, cfull;
cin >> u >> v >> c1 >> cfull;
adj[u].push_back(v);
adj[v].push_back(u);
if (u > v) swap(u, v);
edges[i] = {u, v, c1, cfull};
}
sort(edges + 1, edges + numNode);
dfs(1);
for (int i = 2; i <= numNode; ++i) {
int u = i - 1, v = i;
++pref[par[u]];
++pref[par[v]];
pref[par[lca(u, v)]] -= 2;
}
dfs2(1);
long long res = 0;
for (int i = 1; i < numNode; ++i) {
long long a = 1LL * edges[i].cost1 * pref[i];
long long b = edges[i].costfull;
res += min(a, b);
}
cout << res << '\n';
return 0;
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:13:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define file(name) freopen(name".inp", "r", stdin);\
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:86:2: note: in expansion of macro 'file'
86 | file("BEER");
| ^~~~
putovanje.cpp:14:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:86:2: note: in expansion of macro 'file'
86 | file("BEER");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
16424 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
16436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
16424 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
