#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define pll pair<lli,lli>
#define MAX 200000
//para el vector de stree
#define val first
#define id second
struct x {
lli des;
lli w;
lli comp;
};
lli n,a,b,c,d,raiz,op,total,q,raiz2,op2;
vector<x> hijos[MAX+2];
lli sub[MAX+2],h_op[MAX+2];
vector<lli> res;
//para el euler y el stree
lli papa[MAX+2],vis[MAX+2],offset,cont,aport[MAX+2],lazy[MAX+2];
pll stree[MAX*4],euler[MAX+2];
void push(lli pos) {
if (lazy[pos] == 0) return;
stree[pos].val -= lazy[pos];
if(pos < offset) {
lazy[pos*2] += lazy[pos];
lazy[pos*2+1] += lazy[pos];
}
lazy[pos] = 0;
}
void pre_dfs(lli pos, lli padre) {
for(auto h : hijos[pos]) {
if(h.des == padre) continue;
pre_dfs(h.des,pos);
sub[pos] += sub[h.des] + (h.comp-h.w);
}
}
void def_euler(lli pos, lli padre, lli dis) { // me va a dar tle, necesito un vector donde guarde su aportacion
euler[pos].first = cont++;
stree[ euler[pos].first +offset-1] = {dis,pos};
papa[pos] = padre;
for(auto h : hijos[pos]){
if(h.des == padre) continue;
aport[h.des] = h.w;
def_euler(h.des,pos,dis+h.w);
}
euler[pos].second = cont;
}
void busca_raiz(lli pos, lli padre,lli carga) {
lli a = carga + sub[pos];
if (a > op){
op = a;
raiz = pos;
}
pll mejores[2];
lli act = 0;
for(auto h : hijos[pos]){
if(h.des == padre) continue;
a = carga + sub[pos] - sub[h.des];
a -= (h.comp-h.w);
a += h.w;
busca_raiz(h.des,pos,a);
a = h_op[h.des] + h.w;
if (a > mejores[0].val) {
swap(mejores[0],mejores[1]);
mejores[0] = {a,h.des};
}
else if (a > mejores[1].val) mejores[1] = {a,h.des};
}
a = carga + sub[pos];
a += mejores[0].val + mejores[1].val;
if (a > op2) {
raiz2 = mejores[0].id;
op2 = a;
}
}
void update(lli pos, lli ini, lli fin, lli l, lli r, lli v) {
push(pos);
if (ini > r || fin < l) return;
if (l <= ini && fin <= r) {
lazy[pos] = v;
push(pos);
return;
}
lli mitad = (ini+fin)/2;
update(pos*2,ini,mitad,l,r,v);
update(pos*2+1,mitad+1,fin,l,r,v);
stree[pos] = max(stree[pos*2],stree[pos*2+1]);
}
void solve() {
pll act = stree[1];
op += act.val;
//debugsl(act.val);
//debug(act.id);
if(act.val == 0) return;
lli pos = act.id;
while (vis[pos] == 0) {
vis[pos] = 1;
update(1,1,offset,euler[pos].first, euler[pos].second-1,aport[pos]);
pos = papa[pos];
}
}
void cambia_op(lli pos, lli padre) {
for(auto h : hijos[pos]) {
if (h.des == padre) continue;
op += h.comp - h.w;
cambia_op(h.des,pos);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
rep(i,1,n-1) {
cin >> a >> b >> c >> d;
hijos[a].push_back({b,c,c+d});
hijos[b].push_back({a,d,c+d});
total += (c+d);
}
pre_dfs(1,0);
busca_raiz(1,0,0);
//funciona
res.push_back(total-op);
//ahora tengo que construir el nuevo arbol con el camino euleriano
//sobre el irme acabando las hojas con la mayor distancia a la raiz/algun camino previo
//hacer greedy y al final responder
offset = 1;
while (offset < n) offset *= 2;
cont = 1;
op = 0;
cambia_op(raiz2,0);
def_euler(raiz2,0,0);
repa(pos ,offset-1,1) stree[pos] = max(stree[pos*2], stree[(pos*2)+1]);
while(stree[1].val > 0) {
solve();
res.push_back(total-op);
//rep(i,1,offset-1) push(i);
//rep(i,0,n-1) {debugsl(stree[offset+i].val); debug(stree[offset+i].id);}
//cout << endl;
}
//debug(raiz2);
//for(auto act : res) debug(act);
cin >> q;
rep(i,1,q) {
cin >> a;
a--;
if (a >= res.size()) cout << res[res.size()-1] << "\n";
else cout << res[a] << "\n";
}
return 0;
}
//que no se me ovlide agarrar 2 hojas en la primera pasada (que pasa si no hay 2 hojas)
//las respuestas van uno reccorrido hacia la derecha, entonces checar
//checar que todas las cosas que lo necesiten lleven la funcion de push
Compilation message
designated_cities.cpp: In function 'void busca_raiz(long long int, long long int, long long int)':
designated_cities.cpp:68:9: warning: unused variable 'act' [-Wunused-variable]
68 | lli act = 0;
| ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:180:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | if (a >= res.size()) cout << res[res.size()-1] << "\n";
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Runtime error |
539 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Runtime error |
536 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Runtime error |
539 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
