#include <bits/stdc++.h>
#define MN 100071
#define MK 19
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int n, q, max_weight;
vector<int> L[MN];
map<pair<int, int>, int> W; /// if slow, you may try to make a map for each node
namespace LCA {
const int MB = 3 * MN;
int BIT[MB], tmr, In[MN], Out[MN], Niv[MN];
pair<int, int> RMQ[MK][MB];
int EulerTour[MN];
void bit_up(int p, int v) {
//printf("update bit la poz %d cu %d\n", p, v);
while(p < MB) BIT[p] += v, p += p & (-p);
}
int bit_q_p(int p) {
int re = 0;
while(p) re += BIT[p], p -= p & -p;
return re;
}
int bit_query(int st, int dr) {
return bit_q_p(dr) - (st ? bit_q_p(st - 1) : 0);
}
void dfi(int u, int p, int niv) {
In[u] = Out[u] = ++tmr;
EulerTour[tmr] = u;
Niv[u] = niv;
bit_up(In[u], W[{u, p}]);
for(auto it : L[u]) if(it != p) {
dfi(it, u, niv + 1);
Out[u] = ++tmr;
EulerTour[tmr] = u;
}
if(In[u] == Out[u])
EulerTour[Out[u] = ++tmr] = u;
bit_up(Out[u], -W[{u, p}]);
}
void init() {
dfi(1, 0, 0);
for(int i = 1; i <= tmr; ++i)
RMQ[0][i] = {Niv[EulerTour[i]], EulerTour[i]};
for(int k = 1; k < MK; ++k)
for(int i = 1; i <= tmr; ++i) if(i + (1 << k) - 1<= tmr){
RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1 << (k-1))]);
}
// printf("Euler Tour: "); for(int i = 1; i <= tmr; ++i) printf("%d ", EulerTour[i]);
// printf("\n");
// for(int k = 0; k <= 5; ++k) {
// printf("RMQ %d: ", k); for(int i = 1; i <= n; ++i) printf("(%d, %d); ", RMQ[k][i].first, RMQ[k][i].second);
// printf("\n");
// }
}
inline pair<int, int> rmq_query(int st, int dr) {
assert(st <= dr);
int l = 31 - __builtin_clz(dr - st + 1);
return min(RMQ[l][st], RMQ[l][dr - (1 << l) + 1]);
}
inline int lca(int u, int v) {
return rmq_query(min(In[u], In[v]), max(Out[u], Out[v])).second;
}
inline int dist(int u) {
return bit_q_p(In[u]);
}
inline int dist(int u, int v) {
int l = lca(u, v);
return dist(u) + dist(v) - 2 * dist(l);
}
inline void update(int u, int v, int w) {
if(Niv[u] > Niv[v]) swap(u, v);
bit_up(In[v], w - W[{u, v}]);
bit_up(Out[v], W[{u, v}] - w);
}
}
namespace CENTR {
int Sz[MN], croot, Cpar[MN];
bool Used[MN];
void dfi(int u, int p) {
Sz[u] = 1;
for(auto it : L[u])
if(!Used[it] && it != p)
dfi(it, u), Sz[u] += Sz[it];
}
int find_c(int u, int p, const int &bsz) {
for(auto it : L[u])
if(!Used[it] && it != p && Sz[it] * 2 > bsz) return find_c(it, u, bsz);
return u;
}
using sol = tuple<int, int, int>;
set<sol> BO[MN]; /// perechi {dist, sursa, nod}
map<int, int> DistSursa[MN];
map<int, int> NodSursa[MN];
void desc(int u, int cpar) {
dfi(u, 0);
int c = find_c(u, 0, Sz[u]);
if(!cpar)
croot = c;
Used[c] = 1;
Cpar[c] = cpar;
for(auto it : L[c])
if(!Used[it]) desc(it, c);
}
void afis(sol a) {
printf("%d %d %d ", get<0>(a), get<1>(a), get<2>(a));
}
inline pair<sol, sol> best(int u) {
///imi extrage 2 solutii din u(daca exista) promitatoare
printf("Best sol pt %d : ", u);
if(BO[u].empty()) {
printf("gol\n");
return {{0, 0, 0}, {0, 0, 0}};
}
auto it = BO[u].rbegin();
if(BO[u].size() == 1) {
afis(*it);
printf("\n");
return {*it, {0, 0, 0}};
}
sol a = *it, b; ++it; b = *it;
afis(a), afis(b);
printf("\n");
return {a, b};
}
inline void remove(int u, int l) {
if(!DistSursa[u].count(l)) return;
sol prev = {DistSursa[u][l], l, NodSursa[u][l]};
DistSursa[u].erase(l);
NodSursa[u].erase(l);
BO[u].erase(prev);
}
inline void add(int u, sol a) {
auto &[d, l, v] = a;
sol prev;
if(DistSursa[u].count(l)) {
prev = {DistSursa[u][l], l, NodSursa[u][l]};
} else prev = {0, 0, 0};
if(a > prev) {
DistSursa[u][l] = d;
NodSursa[u][l] = v;
BO[u].erase(prev);
BO[u].insert(a);
}
}
void update(int u) {
int last_source = u, u0 = u;
u = Cpar[u];
while(u) {
remove(u, last_source);
auto [a1, a2] = best(last_source);
sol a3 = {LCA::dist(last_source, u), last_source, last_source};
get<1>(a1) = get<1>(a2) = last_source;
get<0>(a1) = LCA::dist(get<2>(a1), u);
get<0>(a2) = LCA::dist(get<2>(a2), u);
add(u, a1);
add(u, a2);
add(u, a3);
last_source = u;
u = Cpar[u];
}
}
void init() {
desc(1, 0);
for(int i = 1; i <= n; ++i)
update(i);
}
}
ii E[MN];
int main() {
cin >> n >> q >> max_weight;
for(int i = 1, u, v, w; i < n; ++i) {
cin >> u >> v >> w;
E[i] = {u, v};
L[u].push_back(v), L[v].push_back(u);
W[{u, v}] = W[{v, u}] = w;
}
LCA::init();
CENTR::init();
printf("radacina este %d\n", CENTR::croot);
printf("--------------------------\n");
int last = 0;
for(int i = 1; i <= q; ++i) {
int id, w;
cin >> id >> w;
id = (id + last) % (n - 1) + 1;
w = (w + last) % max_weight;
auto &[u, v] = E[id];
LCA::update(u, v, w);
CENTR::update(u);
CENTR::update(v);
auto [b1, b2] = CENTR::best(CENTR::croot);
cout << (last = (get<0>(b1) + get<0>(b2))) << "\n";
}
// int op, u, v, w;
// while(cin >> op >> u >> v) {
// if(op == 1) {
// cin >> w;
// LCA::update(u, v, w);
// } else {
// printf("Pt cele doua nod lca-ul este %d si dist %d\n", LCA::lca(u, v), LCA::dist(u, v));
// }
// }
return 0;
}
Compilation message
diameter.cpp: In function 'void CENTR::update(int)':
diameter.cpp:154:30: warning: unused variable 'u0' [-Wunused-variable]
154 | int last_source = u, u0 = u;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
18256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5022 ms |
18592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
