#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, L;
vector<int> 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 (pli){-INF, -1};
if(l <= s && e <= r) return (pli){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> evt[200009], 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);
evt[in[v]].push_back({+1, c});
evt[ou[v]+1].push_back({-1, c});
}
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);
evt[1].push_back({+1, c});
evt[in[u]].push_back({-1, c});
evt[ou[u] + 1].push_back({+2, c});
}
}
}
int Q; scanf("%d",&Q);
if(Q == 1) {
segtree X = seg;
int E; scanf("%d",&E);
if(E == 1) return !printf("%lld", tot - seg.get(1, 1, N, 1, N).first);
if(E == 2) {
long long ans = 0;
for(int i=1; i<=N; i++) {
for(auto& it: evt[i]) {
int ty, n; tie(ty, n) = it;
for(auto& it: itv[n]) {
int l, r, v; tie(l, r, v) = it;
if(ty > 0) X.upd(1, 1, N, l, r, -v);
else X.upd(1, 1, N, l, r, +v);
}
}
ans = seg.get(1, 1, N, i, i).first + X.get(1, 1, N, 1, N).first;
}
printf("%lld", tot - ans);
}
}
/*
int Q; scanf("%d",&Q);
for(int i=0; i<Q; i++) {
int E; scanf("%d",&E);
int l = 0, r = 1e9; long long f;
for(int m=0; m<=100; m++) {
//int m = l+r >> 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);
printf("interval: %d %d %d\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);
printf("interval: %d %d %d\n", ou[u]+1, in[u]-1, d);
}
}
}
int nk = 0;
long long lans = 0;
while(1) {
long long v; int p; tie(v, p) = seg.get(1, 1, N, 1, N); v -= m;
printf("v: %lld, p: %d\n", v, p);
if(v <= 0) break;
lans += v; ++nk;
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();
}
}
for(int i=1; i<=c; i++) itv[i].clear();
printf("m: %d, nk: %d, lans: %lld\n", m, nk, lans + nk*m);
if(nk <= E) r = m-1, f = lans + E*m;
else l = m+1;
}
printf("%lld\n", tot - f);
}
*/
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:141:17: 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:144:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int E; scanf("%d",&E);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
1903 ms |
130716 KB |
Output is correct |
| 3 |
Correct |
1684 ms |
143252 KB |
Output is correct |
| 4 |
Correct |
1691 ms |
130800 KB |
Output is correct |
| 5 |
Correct |
1836 ms |
130128 KB |
Output is correct |
| 6 |
Execution timed out |
2039 ms |
132520 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19072 KB |
Output is correct |
| 2 |
Execution timed out |
2089 ms |
130572 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
1903 ms |
130716 KB |
Output is correct |
| 3 |
Correct |
1684 ms |
143252 KB |
Output is correct |
| 4 |
Correct |
1691 ms |
130800 KB |
Output is correct |
| 5 |
Correct |
1836 ms |
130128 KB |
Output is correct |
| 6 |
Execution timed out |
2039 ms |
132520 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
