#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#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 debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
#define des first
#define p second
struct x{
lli mayor;
lli lazy;
lli hder;
lli hizq;
};
lli n,q,w,a,b,c,k,last,id,act,ult,sum,l,r;
lli peso[MAX+2];
pair<lli,lli> arr[MAX+2];
vector<pair<lli,lli> > hijos[MAX+2];
vector<lli> iniciales;
pair<lli,lli> rango[MAX+2];
vector<x> st;
multiset<lli> res;
multiset<lli>::iterator it;
lli valores[MAX+2],pertenece[MAX+2];
void recorre(lli pos, lli padre,lli prof) {
rango[pos].first = act;
if (padre == 1) pertenece[pos] = pos;
else pertenece[pos] = pertenece[padre];
bool tiene = false;
for (auto h : hijos[pos]) {
if (h.des == padre) continue;
tiene = true;
recorre(h.des,pos,prof + h.p);
}
if (!tiene) {
act++;
iniciales.push_back(prof);
}
rango[pos].second = act-1;
}
void arma(lli ini, lli fin, lli pos) {
lli mitad;
if (ini == fin) st[pos].mayor = iniciales[ini];
else {
mitad = (ini+fin)/2;
st.push_back({0,0,0,0});
st.push_back({0,0,0,0});
st[pos].hizq = ult;
st[pos].hder = ult+1;
ult += 2;
arma(ini,mitad,st[pos].hizq);
arma(mitad+1,fin,st[pos].hder);
st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
}
}
void aplica(lli pos) {
if (st[pos].lazy != 0) {
if (st[pos].hizq != 0) {
st[ st[pos].hizq ].lazy += st[pos].lazy;
st[ st[pos].hder ].lazy += st[pos].lazy;
}
st[pos].mayor += st[pos].lazy;
st[pos].lazy = 0;
}
}
void actualiza(lli pos, lli ini, lli fin, lli l, lli r, lli val) {
aplica(pos);
if (ini >= l && fin <= r) {
st[pos].lazy += val;
aplica(pos);
}
else if (fin < l || ini > r) return ;
else {
lli mitad = (ini+fin)/2;
actualiza(st[pos].hizq,ini,mitad,l,r,val);
actualiza(st[pos].hder,mitad+1,fin,l,r,val);
st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
}
}
lli query(lli pos, lli ini, lli fin, lli l, lli r) {
aplica(pos);
if (ini >= l && fin <= r) return st[pos].mayor;
else if (ini > r || fin < l) return 0;
else {
lli mitad = (ini+fin)/2;
lli a = query(st[pos].hizq, ini,mitad,l,r);
lli b = query(st[pos].hder, mitad+1,fin,l,r);
return max(a,b);
}
}
lli imprime() {
if (res.size() == 1) {
it = res.begin();
return *it;
}
else {
lli total;
auto itr = res.rbegin();
total = *itr;
itr++;
total += *itr;
return total;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q >> w;
rep(i,1,n-1) {
cin >> a >> b >> c;
arr[i] = {a,b};
peso[i] = c;
hijos[a].push_back({b,c});
hijos[b].push_back({a,c});
}
act = 0;
iniciales.push_back(0);
recorre(1,0,0);
act--;
st.push_back({0,0,0,0});
ult = 1;
arma(1,act,0);
for (auto h : hijos[1]) {
valores[h.des] = query(0,1,act,rango[h.des].first,rango[h.des].second);
res.insert(valores[h.des]);
}
rep(i,1,q) {
//correcto
cin >> id >> c;
id += last;
id %= (n-1);
id++;
c += last;
c %= w;
a = arr[id].first;
b = arr[id].second;
//fill
sum = c - peso[id];
l = max(rango[a].first, rango[b].first);
r = min(rango[a].second, rango[b].second);
if (pertenece[a] != 0) k = pertenece[a];
else k = pertenece[b];
it = res.lower_bound(valores[k]);
res.erase(it);
actualiza(0,1,act,l,r,sum);
valores[k] = query(0,1,act,rango[k].first,rango[k].second);
res.insert(valores[k]);
//last = resultado
last = imprime();
cout << last << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
206 ms |
21532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
