// 07-10-2023
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <time.h>
#include <assert.h>
#include <iomanip>
#include <cstring>
#include <queue>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define BIT(x, i) (1 & ((x) >> (i)))
#define OFF(x, i) ((x) ^ (1 << (i)))
#define ON(x, i) ((x) | (1 << (i)))
#define CNT(x) __builtin_popcountll(x)
#define file(name) \
if (fopen(name ".inp", "r")) \
{ \
freopen(name ".inp", "r", stdin); \
freopen(name ".out", "w", stdout); \
}
#define faster \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const ll N = 200005;
ll n;
ll c[N], d[N], h[N], par[N][25], dp[N], cnt[N], s[N];
vector<pair<ll, ll>> a[N];
void dfs(ll u, ll p, ll t)
{
h[u] = t;
par[u][0] = p;
for (auto v : a[u])
if (v.ff != p)
dfs(v.ff, u, t + 1);
}
ll lca(ll u, ll v)
{
if (h[u] < h[v])
swap(u, v);
ll diff = h[u] - h[v];
for (ll i = 20; i >= 0; i--)
if (BIT(diff, i))
u = par[u][i];
if (u == v)
return u;
for (ll i = 20; i >= 0; i--)
if (par[u][i] != par[v][i])
u = par[u][i], v = par[v][i];
return par[v][0];
}
void calc(ll u, ll p, ll id)
{
for (auto x : a[u])
if (x.ff != p)
calc(x.ff, u, x.ff), dp[u] += dp[x.ff];
dp[u] += s[u], cnt[id] = dp[u];
}
main()
{
faster;
file("tmp");
cin >> n;
ll u, v;
for (ll i = 1; i < n; i++)
{
cin >> u >> v >> c[i] >> d[i];
a[u].push_back({v, i}), a[v].push_back({u, i});
}
dfs(1, 0, 0);
for (ll i = 1; (1 << i) <= n; i++)
for (ll j = 1; j <= n; j++)
par[j][i] = par[par[j][i - 1]][i - 1];
for (ll i = 1; i < n; i++)
s[i]++, s[i + 1]++, s[lca(i, i + 1)] -= 2;
calc(1, 0, 0);
ll ans = 0;
for (ll i = 1; i <= n; i++)
ans += min(cnt[i] * c[i], d[i]);
cout << ans;
}
Compilation message
putovanje.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
69 | main()
| ^~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | freopen(name ".inp", "r", stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:72:5: note: in expansion of macro 'file'
72 | file("tmp");
| ^~~~
putovanje.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen(name ".out", "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:72:5: note: in expansion of macro 'file'
72 | file("tmp");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
42412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
