#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i].st
#define yol g[node][i].nd.st
#define tyol g[node][i].nd.nd
#define mod 10000000000000007
#define inf 10000000000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
typedef pair < ll , ii > iii;
ll n, zu, ans, bir, iki, top, say[N], a[N], x[N], bas[N], son[N], par[N], cvp[N], h[N], lazy[4*N];
ii dp[N], seg[4*N];
vector < iii > g[N];
void hazirla(ll node, ll par){
for(ll i = 0; i < g[node].size(); i++)
if(coc != par){
hazirla(coc, node);
say[node] += say[coc] + tyol;
}
}
void of(ll node, ll par, ll us){
ll top = us + say[node];
cvp[1] = max(cvp[1], top);
ii mx = mp(0, node), mx2 = mp(0, node);
for(ll i = 0; i < g[node].size(); i++)
if(coc != par){
of(coc, node, us + say[node] - (say[coc] + tyol) + yol);
mx2 = max(mx2, mp(-say[coc] - tyol + tyol + yol + dp[coc].st, dp[coc].nd) );
if(mx2 > mx)
swap(mx, mx2);
}
if(top + mx.st + mx2.st > ans){
ans = top + mx.st + mx2.st;
bir = mx.nd;
iki = mx2.nd;
}
if(say[node] + mx.st > ans){
ans = say[node] + mx.st;
bir = mx.nd;
iki = node;
}
dp[node] = mp(say[node] + mx.st, mx.nd);
}
bool bak(ll node, ll pr, ll ara){
if(node == ara){
h[node] = 1;
return 1;
}
bool don = 0;
for(ll i = 0; i < g[node].size(); i++){
if(pr == coc)
continue;
don |= bak(coc, node, ara);
}
if(don)
h[node] = 1;
return don;
}
void dfs(ll node, ll pr, ll us){
bas[node] = ++zu;
if(h[node])
us = 0;
x[zu] = node;
for(ll i = 0; i < g[node].size(); i++){
if(coc == pr)
continue;
par[coc] = node;
dfs(coc, node, us + yol);
}
a[bas[node]] = us;
son[node] = zu;
}
void bu(ll k, ll bas, ll son){
if(bas == son){
seg[k] = mp(a[bas], bas);
return;
}
bu(sol, bas, orta);
bu(sag, orta + 1, son);
seg[k] = max(seg[sol], seg[sag]);
}
void put(ll k, ll bas, ll son, ll z){
seg[k].st += z;
lazy[k] += z;
}
void push(ll k, ll bas, ll son){
put(sol, bas, orta, lazy[k]);
put(sag, orta + 1, son, lazy[k]);
lazy[k] = 0;
}
void up(ll k, ll bas, ll son, ll x, ll y, ll z){
if(bas > y or son < x)
return;
if(bas >= x and son <= y){
put(k, bas, son, z);
return;
}
push(k, bas, son);
up(sol, bas, orta, x, y, z);
up(sag, orta + 1, son, x, y, z);
seg[k] = max(seg[sol], seg[sag]);
}
ii qu(ll k, ll bas, ll son, ll x, ll y){
if(bas > y or son < x)
return mp(0, 0);
if(bas >= x and son <= y)
return seg[k];
push(k, bas, son);
return max(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%lld",&n);
for(ll i = 1; i < n; i++){
ll a, b, c, d;
scanf("%lld %lld %lld %lld",&a ,&b ,&c ,&d);
top += c + d;
g[a].pb(mp(b, mp(c, d)));
g[b].pb(mp(a, mp(d, c)));
}
hazirla(1, 0);
of(1, 0, 0);
// cout << bir << " " << iki << " " << ans << " " << top << endl;
// printf("%lld\n", top - ans);
cvp[2] = top - ans;
bak(bir, 0, iki);
dfs(bir, 0, 0);
bu(1, 1, n);
// for(ll i = 1; i <= n; i++)cout << h[i] << " ";cout << endl;
// for(ll i = 1; i <= n; i++)cout << bas[i] << " -> "<< a[i] << "\n";cout << endl;
for(ll i = 3; i <= n; i++){
ii of = qu(1, 1, n, 1, n);
ans += of.st;
cvp[i] = top - ans;
up(1, 1, n, of.nd, of.nd, -inf);
ll node = par[x[of.nd]];
while(1){
if(h[node] or !node)
break;
up(1, 1, n, bas[node], son[node], -a[bas[node]]);
node = par[node];
}
}
cvp[1] = top - cvp[1];
ll q;
scanf("%lld",&q);
while(q--){
ll x;
scanf("%lld",&x);
printf("%lld\n", cvp[x]);
}
// for(ll i = 1; i <= n; i++)
// cout << i << " " << cvp[i] << endl;
return 0;
}
Compilation message
designated_cities.cpp: In function 'void hazirla(ll, ll)':
designated_cities.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void of(ll, ll, ll)':
designated_cities.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'bool bak(ll, ll, ll)':
designated_cities.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs(ll, ll, ll)':
designated_cities.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
designated_cities.cpp:137: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:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&q);
~~~~~^~~~~~~~~~~
designated_cities.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
35 ms |
23928 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
23804 KB |
Output is correct |
| 2 |
Execution timed out |
2025 ms |
69820 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 2 |
Execution timed out |
2041 ms |
64812 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
35 ms |
23928 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
23804 KB |
Output is correct |
| 2 |
Execution timed out |
2025 ms |
69820 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
35 ms |
23928 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
