#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, pair<int, int> > > adj[200010];
int n;
int dgoingup[200010], dgoingdown[200010], done[200010];
int goingup(int a)
{
if (dgoingup[a]) return dgoingup[a]-1;
dgoingup[a] = 1;
for (auto b : adj[a])
{
if (!dgoingup[b.first]) dgoingup[a] += goingup(b.first), dgoingup[a] += b.second.second;
}
return dgoingup[a]-1;
}
int goingdown(int a)
{
if (dgoingdown[a]) return dgoingdown[a]-1;
dgoingdown[a] = 1;
for (auto b : adj[a])
{
if (!dgoingdown[b.first]) dgoingdown[a] += goingdown(b.first), dgoingdown[a] += b.second.first;
}
return dgoingdown[a]-1;
}
int oneans = 1e15;
void findoneans(int a, int above)
{
done[a] = 1;
int am = 0;
for (auto b : adj[a])
{
if (done[b.first]) continue;
am += goingup(b.first)+b.second.second;
}
oneans = min(oneans, am+above);
for (auto b : adj[a])
{
if (done[b.first]) continue;
findoneans(b.first, above+am-goingup(b.first)-b.second.second + b.second.first);
}
}
int jump[200010][20], root, seen[200010], cost[200010], hei[200010], cost2[200010];
int roots[200010], revroots[200010], upto;
void dfs(int a, int am, int am2)
{
seen[a] = 1;
cost[a] = am;
cost2[a] = am2;
//printf("%d, %d\n", a, cost[a]);
for (auto b : adj[a])
{
if (seen[b.first]) continue;
jump[b.first][0] = a;
hei[b.first] = hei[a]+1;
dfs(b.first, am+b.second.second, am2+b.second.first);
}
if (adj[a].size() == 1)
{
roots[a] = upto;
revroots[upto++] = a;
}
}
int ans[200010];
int lca(int a, int b)
{
for (int i = 19; i >= 0; i--)
{
if (hei[jump[a][i]] >= hei[b]) a = jump[a][i];
if (hei[jump[b][i]] >= hei[a]) b = jump[b][i];
}
if (a == b) return a;
for (int i = 19; i >= 0; i--)
{
if (jump[a][i] != jump[b][i]) a = jump[a][i], b = jump[b][i];
}
assert(a != b && jump[a][0] == jump[b][0]);
return jump[a][0];
}
#undef int
int main()
{
#define int long long
scanf("%lld", &n);
for (int i = 1; i < n; i++)
{
int a, b, c, d;
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
a--;
b--;
adj[a].push_back({ b, { d, c }});
adj[b].push_back({ a, { c, d }});
}
goingup(0), goingdown(0), findoneans(0, 0);
ans[1] = oneans;
for (int i = 0; i < n; i++)
{
if (adj[i].size() != 1)
{
root = i;
break;
}
}
hei[root] = 1;
dfs(root, 0, 0);
for (int j = 1; j < 20; j++)
{
for (int i = 0; i < n; i++)
{
jump[i][j] = jump[jump[i][j-1]][j-1];
}
}
set<int> in;
for (int i = 0; i < upto; i++) in.insert(i);
for (int i = upto-1; i > 1; i--)
{
// want to remove something from in
int pre = -1;
pair<int, int> mn = { 1e15, -1 };
for (auto it = in.begin(); it != in.end(); ++it)
{
auto nex = next(it);
int l;
int extra = 0;
if (nex == in.end())
{
int l1 = lca(revroots[*it], revroots[pre]);
int l2 = lca(revroots[*in.begin()], revroots[pre]);
extra = cost2[l2]-cost2[l1];
l = l1;
}
else if (pre == -1)
{
int l2 = lca(revroots[*it], revroots[*nex]);
l = l2;
}
else
{
int l1 = lca(revroots[*it], revroots[pre]);
int l2 = lca(revroots[*it], revroots[*nex]);
if (hei[l1] > hei[l2]) l = l1;
else l = l2;
}
int am = cost[revroots[*it]] - cost[l] + extra;
// printf("%lld (%lld) lca %lld, cost %lld\n", *it, revroots[*it], l, am);
mn = min(mn, { am, *it });
pre = *it;
}
assert(mn.second != -1);
// printf("%lld (%lld) %lld\n\n", mn.second, revroots[mn.second], mn.first);
in.erase(mn.second);
ans[i] = ans[i+1]+mn.first;
}
int q;
scanf("%lld", &q);
for (int i = 0; i < q; i++)
{
int a;
scanf("%lld", &a);
printf("%lld\n", ans[a]);
}
}
Compilation message
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
designated_cities.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &q);
~~~~~^~~~~~~~~~~~
designated_cities.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
2023 ms |
66416 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
2057 ms |
66444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
2023 ms |
66416 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
