#include <bits/stdc++.h>
using namespace std;
using pli = pair<long long, int>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const long long INF = 1LL * 1e18;
struct segtree {
vector<long long> T;
vector<int> L, P;
void init(int idx, int s, int e) {
if(s == e) {
P[idx] = s;
return;
}
int m = s+e >> 1;
init(idx*2, s, m);
init(idx*2+1, m+1, e);
}
void upd_lazy(int idx, int s, int e) {
if(L[idx]) {
T[idx] += L[idx];
if(s != e) {
L[idx*2] += L[idx];
L[idx*2+1] += L[idx];
}
L[idx] = 0;
}
}
pli get(int idx, int s, int e, int l, int r) {
upd_lazy(idx, s, e);
if(r < s || e < l) return (pii){-INF, -1};
if(l <= s && e <= r) return (pii){T[idx], P[idx]};
int m = s+e >> 1;
pli L = get(idx*2, s, m, l, r), R = get(idx*2+1, m+1, e, l, r);
if(L.first > R.first) return L;
return R;
}
void upd(int idx, int s, int e, int l, int r, int v) {
upd_lazy(idx, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r) {
L[idx] += v;
upd_lazy(idx, s, e);
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, l, r, v);
upd(idx*2+1, m+1, e, l, r, v);
T[idx] = max(T[idx*2], T[idx*2+1]);
if(T[idx*2] > T[idx*2+1]) P[idx] = P[idx*2];
else P[idx] = P[idx*2+1];
}
segtree(int sz) {
T.resize(4*sz);
L.resize(4*sz);
P.resize(4*sz);
init(1, 1, sz);
}
};
struct MergeSortTree {
vector<vector<int> > T;
vector<int> get(int idx, int s, int e, int p) {
if(p < s || e < p) return vector<int>();
int m = s+e >> 1;
vector<int> ret = T[idx]; //T[idx].clear();
if(s == e) return ret;
for(auto& it: get(idx*2, s, m, p)) ret.push_back(it);
for(auto& it: get(idx*2+1, m+1, e, p)) ret.push_back(it);
return ret;
}
void upd(int idx, int s, int e, int l, int r, int x) {
if(r < s || e < l) return;
if(l <= s && e <= r) {
T[idx].push_back(x);
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, l, r, x);
upd(idx*2+1, m+1, e, l, r, x);
}
MergeSortTree(int sz) {
T.resize(4*sz, vector<int>());
}
};
vector<pii> adj[200009];
vector<tiii> itv[400009];
int in[200009], ou[200009], t;
void dfs(int x, int p) {
in[x] = ++t;
for(auto& it: adj[x]) {
if(it.first != p) {
dfs(it.first, x);
}
}
ou[x] = t;
}
int main() {
long long tot = 0;
int N; scanf("%d",&N);
for(int i=0; i<N-1; i++) {
int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
adj[a].push_back({b, c});
adj[b].push_back({a, d});
tot += c + d;
}
dfs(1, 1);
int c = 0;
MergeSortTree MST(N); segtree seg(N);
for(int i=1; i<=N; i++) {
for(auto& it: adj[i]) {
int u = i, v = it.first, d = it.second;
if(in[u] < in[v]) { // u is parent
itv[++c].push_back((tiii){in[v], ou[v], d});
MST.upd(1, 1, N, in[v], ou[v], c);
seg.upd(1, 1, N, in[v], ou[v], d);
}
else { // v is parent
itv[++c].push_back((tiii){1, in[u] - 1, d});
itv[c].push_back((tiii){ou[u] + 1, N, d});
MST.upd(1, 1, N, 1, in[u] - 1, c);
MST.upd(1, 1, N, ou[u] + 1, N, c);
seg.upd(1, 1, N, 1, in[u] - 1, d);
seg.upd(1, 1, N, ou[u] + 1, N, d);
}
}
}
int Q; scanf("%d",&Q);
for(int i=0; i<Q; i++) {
int E; scanf("%d",&E);
long long ans = tot;
while(E--) {
long long v; int p; tie(v, p) = seg.get(1, 1, N, 1, N);
ans -= v;
vector<int> er = MST.get(1, 1, N, p);
for(auto& it: er) {
for(auto& jt: itv[it]) {
int l, r, v; tie(l, r, v) = jt;
seg.upd(1, 1, N, l, r, -v);
}
itv[it].clear();
}
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
designated_cities.cpp: In member function 'void segtree::init(int, int, int)':
designated_cities.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
designated_cities.cpp: In member function 'pli segtree::get(int, int, int, int, int)':
designated_cities.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
designated_cities.cpp: In member function 'void segtree::upd(int, int, int, int, int, int)':
designated_cities.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
designated_cities.cpp: In member function 'std::vector<int> MergeSortTree::get(int, int, int, int)':
designated_cities.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
designated_cities.cpp: In member function 'void MergeSortTree::upd(int, int, int, int, int, int)':
designated_cities.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
designated_cities.cpp:108:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int Q; scanf("%d",&Q);
~~~~~^~~~~~~~~
designated_cities.cpp:138:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int E; scanf("%d",&E);
~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
1797 ms |
103884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
1785 ms |
104236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
1797 ms |
103884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
