#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 2e5+10;
int n;
ll ans;
int tab[maxn][20], nivel[maxn];
int val[maxn];
vector<int> grafo[maxn];
map<pii, int> c1, c2;
void dfs(int u, int p)
{
for (auto v: grafo[u])
{
if (v != p)
{
nivel[v] = nivel[u]+1, tab[v][0] = u;
dfs(v, u);
}
}
}
void build(void)
{
for (int j = 1; j < 20; j++)
for (int i = 1; i <= n; i++)
tab[i][j] = tab[tab[i][j-1]][j-1];
}
int lca(int u, int v)
{
if (nivel[u] < nivel[v]) swap(u, v);
for (int i = 19; i >= 0; i--)
if (nivel[u]-(1<<i) >= nivel[v])
u = tab[u][i];
if (u == v) return u;
for (int i = 19; i >= 0; i--)
if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
u = tab[u][i], v = tab[v][i];
return tab[u][0];
}
int solve(int u, int p)
{
int tot = val[u];
for (auto v: grafo[u])
if (v != p)
tot += solve(v, u);
if (u != 1)
{
if (1ll*tot*c1[{u, p}] > c2[{u, p}])
ans += 1ll*c2[{u, p}];
else
ans += 1ll*tot*c1[{u, p}];
}
return tot;
}
int main(void)
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v, a, b;
scanf("%d %d %d %d", &u, &v, &a, &b);
grafo[u].push_back(v), grafo[v].push_back(u);
c1[{u, v}] = c1[{v, u}] = a, c2[{u, v}] = c2[{v, u}] = b;
}
dfs(1, 0); build();
for (int i = 1; i < n; i++)
{
val[i]++, val[i+1]++;
val[lca(i, i+1)] -= 2;
}
solve(1, 0);
printf("%lld\n", ans);
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
putovanje.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &u, &v, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4984 KB |
Output is correct |
2 |
Correct |
12 ms |
5624 KB |
Output is correct |
3 |
Correct |
13 ms |
5880 KB |
Output is correct |
4 |
Correct |
13 ms |
5752 KB |
Output is correct |
5 |
Correct |
15 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5112 KB |
Output is correct |
7 |
Correct |
9 ms |
5240 KB |
Output is correct |
8 |
Correct |
11 ms |
5496 KB |
Output is correct |
9 |
Correct |
12 ms |
5756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
495 ms |
41592 KB |
Output is correct |
2 |
Correct |
476 ms |
44152 KB |
Output is correct |
3 |
Correct |
521 ms |
47356 KB |
Output is correct |
4 |
Correct |
595 ms |
48120 KB |
Output is correct |
5 |
Correct |
9 ms |
5240 KB |
Output is correct |
6 |
Correct |
455 ms |
41568 KB |
Output is correct |
7 |
Correct |
280 ms |
31608 KB |
Output is correct |
8 |
Correct |
508 ms |
42616 KB |
Output is correct |
9 |
Correct |
229 ms |
44532 KB |
Output is correct |
10 |
Correct |
232 ms |
43384 KB |
Output is correct |
11 |
Correct |
242 ms |
46456 KB |
Output is correct |
12 |
Correct |
237 ms |
46456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4984 KB |
Output is correct |
2 |
Correct |
12 ms |
5624 KB |
Output is correct |
3 |
Correct |
13 ms |
5880 KB |
Output is correct |
4 |
Correct |
13 ms |
5752 KB |
Output is correct |
5 |
Correct |
15 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5112 KB |
Output is correct |
7 |
Correct |
9 ms |
5240 KB |
Output is correct |
8 |
Correct |
11 ms |
5496 KB |
Output is correct |
9 |
Correct |
12 ms |
5756 KB |
Output is correct |
10 |
Correct |
495 ms |
41592 KB |
Output is correct |
11 |
Correct |
476 ms |
44152 KB |
Output is correct |
12 |
Correct |
521 ms |
47356 KB |
Output is correct |
13 |
Correct |
595 ms |
48120 KB |
Output is correct |
14 |
Correct |
9 ms |
5240 KB |
Output is correct |
15 |
Correct |
455 ms |
41568 KB |
Output is correct |
16 |
Correct |
280 ms |
31608 KB |
Output is correct |
17 |
Correct |
508 ms |
42616 KB |
Output is correct |
18 |
Correct |
229 ms |
44532 KB |
Output is correct |
19 |
Correct |
232 ms |
43384 KB |
Output is correct |
20 |
Correct |
242 ms |
46456 KB |
Output is correct |
21 |
Correct |
237 ms |
46456 KB |
Output is correct |
22 |
Correct |
635 ms |
41420 KB |
Output is correct |
23 |
Correct |
535 ms |
37240 KB |
Output is correct |
24 |
Correct |
630 ms |
41080 KB |
Output is correct |
25 |
Correct |
10 ms |
5368 KB |
Output is correct |
26 |
Correct |
210 ms |
22140 KB |
Output is correct |
27 |
Correct |
494 ms |
35832 KB |
Output is correct |
28 |
Correct |
199 ms |
40312 KB |
Output is correct |
29 |
Correct |
237 ms |
46456 KB |
Output is correct |
30 |
Correct |
242 ms |
46456 KB |
Output is correct |
31 |
Correct |
11 ms |
5624 KB |
Output is correct |