#include <bits/stdc++.h>
using namespace std;
#define MAX 410000
long long n, par[25][MAX], first[MAX], last[MAX], tym, br[25][MAX], tree[MAX * 2], lazy[MAX * 2];
map<pair<int, int>, long long > mp;
long long ans;
vector <int> gr[MAX];
bool used[MAX];
struct edge
{
long long a, b, c, d;
} e[MAX];
void dfs(int v, int pr)
{
used[v] = true;
first[v] = ++tym;
par[0][v] = pr;
for(int i = 1; i < 25; i++)
{
par[i][v] = par[i - 1][par[i - 1][v]];
}
for(int i = 0; i < gr[v].size(); i++)
{
if(!used[gr[v][i]])
{
dfs(gr[v][i], v);
}
}
last[v] = ++tym;
return;
}
bool ancestor(int a, int b)
{
return (first[a] <= first[b] && last[b] <= last[a]);
}
void lca(int a, int b)
{
int tmp = a;
for(int i = 24; i >= 0; i--)
{
if(!ancestor(par[i][tmp], b))
{
br[i][tmp]++;
tmp = par[i][tmp];
}
}
if(!ancestor(tmp, b))br[0][tmp]++;
tmp = b;
for(int i = 24; i >= 0; i--)
{
if(!ancestor(par[i][tmp], a))
{
br[i][tmp]++;
tmp = par[i][tmp];
}
}
if(!ancestor(tmp, a))br[0][tmp]++;
return ;
}
void update(int v, int l, int r, int ql, int qr, int val)
{
if(lazy[v] != 0)
{
if(v * 2 + 1 < 2 * MAX)
{
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
tree[v] += (r - l + 1) * lazy[v];
lazy[v] = 0;
}
if(ql <= l && r <= qr)
{
if(v * 2 + 1 < 2 * MAX)
{
lazy[v * 2] += val;
lazy[v * 2 + 1] += val;
}
tree[v] += (r - l + 1) * val;
return;
}
if(l > qr || r < ql)return ;
int mid = (l + r) / 2;
update(v * 2, l, mid, ql, qr, val);
update(v * 2 + 1, mid + 1, r, ql, qr, val);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
return;
}
int query(int v, int l, int r, int ql, int qr)
{
if(lazy[v] != 0)
{
if(v * 2 + 1 < 2 * MAX)
{
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
tree[v] += (r - l + 1) * lazy[v];
lazy[v] = 0;
}
if(ql <= l && r <= qr)
{
return tree[v];
}
if(l > qr || r < ql)return 0;
int mid = (l + r) / 2;
return query(v * 2, l, mid, ql, qr) +
query(v * 2 + 1, mid + 1, r, ql, qr);
}
void dfs_comp(int v, int depth, int par)
{
used[v] = 1;
int q = query(1, 1, n, depth, depth);
update(1, 1, n, depth, depth, -q);
for(int i = 0; i < gr[v].size(); i++)
{
if(!used[gr[v][i]])
{
dfs_comp(gr[v][i], depth + 1, v);
}
}
for(int i = 0; i < 25; i++)
{
update(1, 1, n, max(1, depth - (1 << i) + 1), depth, br[i][v]);
}
int num = query(1, 1, n, depth, depth);
mp[{par, v}] = mp[{v, par}] = num;
return ;
}
int main()
{
scanf("%lld", &n);
for(int i = 0; i < n - 1; i++)
{
scanf("%lld%lld%lld%lld", &e[i].a, &e[i].b, &e[i].c, &e[i].d);
gr[e[i].a].push_back(e[i].b);
gr[e[i].b].push_back(e[i].a);
}
dfs(1, 0);
last[0] = INT_MAX;
for(int i = 1; i <= n - 1; i++)
{
lca(i, i + 1);
}
fill(used, used + n + 2, 0);
dfs_comp(1, 1, 0);
for(int i = 0; i < n - 1; i++)
{
int tmp = mp[{e[i].a, e[i].b}];
if(tmp * e[i].c > e[i].d)ans += e[i].d;
else ans += tmp * e[i].c;
}
printf("%lld\n", ans);
return 0;
}
Compilation message
putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < gr[v].size(); i++)
| ~~^~~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs_comp(int, int, int)':
putovanje.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < gr[v].size(); i++)
| ~~^~~~~~~~~~~~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
155 | scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
putovanje.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | scanf("%lld%lld%lld%lld", &e[i].a, &e[i].b, &e[i].c, &e[i].d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10196 KB |
Output is correct |
2 |
Correct |
12 ms |
11028 KB |
Output is correct |
3 |
Correct |
15 ms |
11176 KB |
Output is correct |
4 |
Correct |
11 ms |
11104 KB |
Output is correct |
5 |
Correct |
11 ms |
11128 KB |
Output is correct |
6 |
Correct |
5 ms |
10324 KB |
Output is correct |
7 |
Correct |
8 ms |
10488 KB |
Output is correct |
8 |
Correct |
9 ms |
10836 KB |
Output is correct |
9 |
Correct |
11 ms |
11092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
842 ms |
66440 KB |
Output is correct |
2 |
Correct |
863 ms |
70200 KB |
Output is correct |
3 |
Correct |
954 ms |
75660 KB |
Output is correct |
4 |
Correct |
980 ms |
77940 KB |
Output is correct |
5 |
Correct |
7 ms |
10596 KB |
Output is correct |
6 |
Correct |
826 ms |
66876 KB |
Output is correct |
7 |
Correct |
507 ms |
50652 KB |
Output is correct |
8 |
Correct |
839 ms |
68216 KB |
Output is correct |
9 |
Correct |
617 ms |
59688 KB |
Output is correct |
10 |
Correct |
589 ms |
58304 KB |
Output is correct |
11 |
Correct |
653 ms |
62228 KB |
Output is correct |
12 |
Correct |
647 ms |
62244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10196 KB |
Output is correct |
2 |
Correct |
12 ms |
11028 KB |
Output is correct |
3 |
Correct |
15 ms |
11176 KB |
Output is correct |
4 |
Correct |
11 ms |
11104 KB |
Output is correct |
5 |
Correct |
11 ms |
11128 KB |
Output is correct |
6 |
Correct |
5 ms |
10324 KB |
Output is correct |
7 |
Correct |
8 ms |
10488 KB |
Output is correct |
8 |
Correct |
9 ms |
10836 KB |
Output is correct |
9 |
Correct |
11 ms |
11092 KB |
Output is correct |
10 |
Correct |
842 ms |
66440 KB |
Output is correct |
11 |
Correct |
863 ms |
70200 KB |
Output is correct |
12 |
Correct |
954 ms |
75660 KB |
Output is correct |
13 |
Correct |
980 ms |
77940 KB |
Output is correct |
14 |
Correct |
7 ms |
10596 KB |
Output is correct |
15 |
Correct |
826 ms |
66876 KB |
Output is correct |
16 |
Correct |
507 ms |
50652 KB |
Output is correct |
17 |
Correct |
839 ms |
68216 KB |
Output is correct |
18 |
Correct |
617 ms |
59688 KB |
Output is correct |
19 |
Correct |
589 ms |
58304 KB |
Output is correct |
20 |
Correct |
653 ms |
62228 KB |
Output is correct |
21 |
Correct |
647 ms |
62244 KB |
Output is correct |
22 |
Correct |
622 ms |
54976 KB |
Output is correct |
23 |
Correct |
558 ms |
49608 KB |
Output is correct |
24 |
Correct |
606 ms |
54116 KB |
Output is correct |
25 |
Correct |
8 ms |
10728 KB |
Output is correct |
26 |
Correct |
229 ms |
30600 KB |
Output is correct |
27 |
Correct |
506 ms |
47816 KB |
Output is correct |
28 |
Correct |
537 ms |
54488 KB |
Output is correct |
29 |
Correct |
637 ms |
62412 KB |
Output is correct |
30 |
Correct |
629 ms |
62992 KB |
Output is correct |
31 |
Correct |
10 ms |
10964 KB |
Output is correct |