#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int MAXN = 200'009;
const int INF = 1e9;
struct SegTree {
const static int T = 1<<19;
pii t[2*T];
int lz[2*T];
void push(int v) {
t[2*v].st += lz[v];
lz[2*v] += lz[v];
t[2*v+1].st += lz[v];
lz[2*v+1] += lz[v];
lz[v] = 0;
}
void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) {
//if(v==1) cerr << l << " " << r << " " << val << "\n";
if(l>r) return;
if(l==tl&&r==tr) {
//cerr << "adding: " << v << " " << val << "\n";
t[v].st += val;
lz[v] += val;
//cerr << "new: " << t[v] << "\n";
return;
}
int tm = (tl+tr)/2;
push(v);
update(l, min(r, tm), val, tl, tm, 2*v);
update(max(l, tm+1), r, val, tm+1, tr, 2*v+1);
t[v] = max(t[2*v], t[2*v+1]);
}
pii query(int l, int r, int tl=0, int tr=T-1, int v=1) {
//cerr << "query: " << l << " " << r << " " << v << " "<<t[v] << "\n";
if(l>r) return {-INF, -1};
if(l==tl&&r==tr) return t[v];
int tm = (tl+tr)/2;
push(v);
return max(query(l, min(r, tm), tl, tm, 2*v),
query(max(l, tm+1), r, tm+1, tr, 2*v+1));
}
} seg, seg1, seg2;
int n;
vector<pair<int, pii>> G[MAXN];
int tin[MAXN], tout[MAXN], T;
int sum[MAXN];
int heavy[MAXN];
int head[MAXN];
int pos[MAXN], P;
int par[MAXN];
pii cost[MAXN];
pii dp[MAXN];
void dfs(int x, int p=-1) {
par[x] = p;
tin[x] = ++T;
seg.t[tin[x]+seg.T].nd = x;
seg.update(tin[x], tin[x], INF);
for(auto [y, c]:G[x]) {
if(y==p)
continue;
cost[y] = c;
sum[x] += c.nd;
dfs(y, x);
sum[x] += sum[y];
}
tout[x] = ++T;
seg.t[tout[x]+seg.T].nd = x;
seg.update(tout[x], tout[x], INF);
for(auto [y, c]:G[x]) {
if(y==p) continue;
//cerr << "updates: " << x << " " << y << "\n";
seg.update(tin[y], tout[y], c.st);
seg.update(1, tin[y]-1, c.nd);
seg.update(tout[y]+1, 2*n, c.nd);
}
}
pair<int, pii> start;
void dfs2(int x, int p=-1, int s=0) {
pii best[2];
best[0] = {0, x};
best[1].st = -INF;
for(auto [y, c]:G[x]) {
if(y==p) continue;
dfs2(y, x, s+c.st+sum[x]-sum[y]-c.nd);
int val = dp[y].st+c.st+c.nd-sum[y]-c.nd;
if(val>=best[0].st) {
best[1] = best[0];
best[0] = {val, dp[y].nd};
} else if(val>=best[1].st) {
best[1] = {val, dp[y].nd};
}
}
start = max(start, {best[0].st+best[1].st+s+sum[x],
{best[0].nd, best[1].nd}});
dp[x] = {sum[x], x};
for(auto [y, c]:G[x]) {
if(y==p) continue;
dp[x] = max(dp[x],
{dp[y].st+c.st+c.nd+sum[x]-sum[y]-c.nd, dp[y].nd});
}
}
int dfs3(int x, int p=-1) {
int s = 1;
int max_s = 0;
for(auto [y, c]:G[x]) {
if(y==p) continue;
int c_s = dfs3(y, x);
s += c_s;
if(c_s>max_s) {
max_s = c_s;
heavy[x] = y;
}
}
return s;
}
void decompose(int x, int h, int p=-1) {
head[x] = h;
pos[x] = P++;
if(heavy[x]!=0)
decompose(heavy[x], h, x);
for(auto [y, c]:G[x]) {
if(y!=p&&y!=heavy[x])
decompose(y, y, x);
}
//cerr << "hld: " << x << "->" << pos[x] << "\n";
}
int ans[MAXN];
void erase_e(int x, int type) {
//cerr << "erasing edge: " << x << " " << type << "\n";
if(type==0) {
seg.update(1, tin[x]-1, -cost[x].nd);
seg.update(tout[x]+1, 2*n, -cost[x].nd);
seg1.update(pos[x], pos[x], -INF);
}
if(type==1) {
seg.update(tin[x], tout[x], -cost[x].st);
seg2.update(pos[x], pos[x], -INF);
}
}
void erase_v(int x) {
//cerr << "erasing v: " << x << "\n";
seg.update(tin[x], tin[x], -INF);
seg.update(tout[x], tout[x], -INF);
vector<pii> segments;
int cur = x;
while(cur!=-1) {
segments.pb({pos[head[cur]], pos[cur]});
cur = par[head[cur]];
}
reverse(all(segments));
for(pii x:segments) {
//cerr << x.st << " " << x.nd << "\n";
}
int pre = 0;
for(pii x:segments) {
pii y = seg1.query(pre, x.st-1);
//cerr << "querying: "<< pre << " " << x.st-1 << "\n";
while(y.st>0) {
erase_e(y.nd, 0);
y = seg1.query(pre, x.st-1);
}
pre = x.nd+1;
}
pii Y = seg1.query(pre, n);
while(Y.st>0) {
erase_e(Y.nd, 0);
Y = seg1.query(pre, n);
}
for(pii x:segments) {
pii y = seg2.query(x.st, x.nd);
while(y.st>0) {
erase_e(y.nd, 1);
y = seg2.query(x.st, x.nd);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for(int i=0;i<2*seg.T;i++) {
seg.t[i].st = -INF;
}
cin >> n;
int S = 0;
for(int i=0;i<n-1;i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
S += c+d;
G[a].pb({b, {c, d}});
G[b].pb({a, {d, c}});
}
dfs(1);
dfs2(1);
dfs3(1);
decompose(1, 1);
for(int i=2;i<=n;i++) {
seg1.t[pos[i]+seg1.T].nd = i;
seg1.update(pos[i], pos[i], cost[i].nd);
seg2.t[pos[i]+seg2.T].nd = i;
seg2.update(pos[i], pos[i], cost[i].nd);
}
//cerr << "cos: " << tin[2] << "\n";
ans[1] = seg.query(1, 2*n).st;
ans[2] = start.st;
erase_v(start.nd.st);
erase_v(start.nd.nd);
for(int i=3;i<=n;i++) {
//cerr << seg.query(tin[2], tin[2]).st << " xd\n";
//cerr << seg.query(tin[0], tin[0]).st << " xd\n";
pii x = seg.query(1, 2*n);
//cerr << "New year, new me " << x.nd << "\n";
//cerr << "with some weird value: " << x.st << "\n";
ans[i] = ans[i-1] + x.st;
erase_v(x.nd);
}
int q;
cin >> q;
while(q--) {
int x;
cin >> x;
cout << S-ans[x] << "\n";
}
}
Compilation message
designated_cities.cpp: In function 'void erase_v(int)':
designated_cities.cpp:169:10: warning: variable 'x' set but not used [-Wunused-but-set-variable]
169 | for(pii x:segments) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
35420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 2 |
Incorrect |
1969 ms |
61048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 2 |
Incorrect |
1870 ms |
62588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
35420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 2 |
Incorrect |
1969 ms |
61048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
35420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
