#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];
}
int done2[200010], cans, ambelowsave[200010];
int ambelow(int a, int bit)
{
if (ambelowsave[a]) return ambelowsave[a]-1;
ambelowsave[a] = 1;
for (auto b : adj[a])
{
if (!ambelowsave[b.first])
{
ambelowsave[a] += ambelow(b.first, bit);
}
}
if (adj[a].size() == 1)
{
if (bit & (1 << roots[a])) ambelowsave[a]++;
}
return ambelowsave[a]-1;
}
void dothing(int a, int amabove, int bit)
{
done2[a] = bit;
for (auto b : adj[a])
{
if (done2[b.first] == bit) continue;
amabove += ambelow(b.first, bit);
}
for (auto b : adj[a])
{
if (done2[b.first] == bit) continue;
int newamabove = amabove - ambelow(b.first, bit);
if (newamabove) // goingup
{
cans += b.second.first;
}
if (newamabove != amabove)
{
cans += b.second.second;
}
dothing(b.first, newamabove, bit);
}
}
#undef int
int main()
{
#define int long long
scanf("%lld", &n);
int total = 0;
for (int i = 1; i < n; i++)
{
int a, b, c, d;
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
total += c;
total += 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];
}
}
fill_n(ans+2, upto-1, (int)(1e15));
for (int bit = 0; bit < (1 << upto); bit++)
{
if (__builtin_popcountll(bit) <= 1) continue;
cans = 0;
fill_n(ambelowsave, n, 0);
ambelow(root, bit);
dothing(root, 0, bit);
ans[__builtin_popcountll(bit)] = min(ans[__builtin_popcountll(bit)], total-cans);
}
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:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
designated_cities.cpp:131: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:169:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &q);
~~~~~^~~~~~~~~~~~
designated_cities.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
2045 ms |
66468 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
2045 ms |
66468 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
