#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<int> frati[NMAX];
map<pair<int, int>, vector<pair<int, int> > > mp;
bool dead[NMAX], mark[NMAX], viz[NMAX];
int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
ll dist[NMAX], maxx[NMAX];
struct SEGTREE
{
vector<ll> Arb, lazy;
vector<int> in, out;
int cati;
inline void init(int n)
{
cati = n;
int put = 1;
while(put <= n)
put <<= 1;
put <<= 1;
Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put << 1);
}
inline void build(int nod, int st, int dr)
{
if(st == dr)
{
Arb[nod] = dist[st];
return;
}
int mij = (st + dr) / 2;
build(2 * nod, st, mij);
build(2 * nod + 1, mij + 1, dr);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline void push(int nod){
if(lazy[nod]){
Arb[nod] += lazy[nod];
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
lazy[nod] = 0;
}
}
inline void update(int nod, int st, int dr, int a, int b, ll val){
if(a <= st && dr <= b){
lazy[nod] += val;
push(nod);
return;
}
push(nod);
int mij = (st + dr) / 2;
if(a <= mij)
update(2 * nod, st, mij, a, b, val);
if(b > mij)
update(2 * nod + 1, mij + 1, dr, a, b, val);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline ll query(int nod, int st, int dr, int a, int b){
push(nod);
if(a <= st && dr <= b)
return Arb[nod];
int mij = (st + dr) / 2;
ll rez1 = 0, rez2 = 0;
if(a <= mij)
rez1 = query(2 * nod, st, mij, a, b);
if(b > mij)
rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
return max(rez1, rez2);
}
} interv[NMAX];
inline int getC(int nod)
{
viz[nod] = 1;
sz[nod] = 1;
int maxx = 0;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
{
int c = getC(it.first);
if(c != -1)
return c;
sz[nod] += sz[it.first];
maxx = max(maxx, sz[it.first]);
}
maxx = max(maxx, dim - sz[nod]);
if(maxx <= dim / 2)
return nod;
return -1;
}
inline void DFS(int nod)
{
viz[nod] = 1;
tip[nod] = cnt;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
DFS(it.first);
}
inline void buildTree(int nod, int tata = -1)
{
interv[baza].in[id[nod]] = ++mov;
for(auto it: G[nod])
if(tata != it.first && mark[it.first])
{
mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza});
dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second;
buildTree(it.first, nod);
}
interv[baza].out[id[nod]] = mov;
}
inline void centroidDecomp(vector<int> nodes)
{
if(nodes.size() == 1)
return;
int mr = 0;
for(auto it: nodes)
mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr;
dim = nodes.size();
int cen = getC(nodes[0]);
baza = cen;
mov = dist[1] = 0;
interv[baza].init(nodes.size());
buildTree(cen);
interv[baza].build(1, 1, nodes.size());
for(auto it: nodes)
viz[it] = 0;
viz[cen] = 1;
cnt = 0;
for(auto it: G[cen])
if(!viz[it.first] && mark[it.first])
{
frati[cen].push_back(id[it.first]);
++cnt;
DFS(it.first);
}
vector<vector<int> > nex(cnt + 1);
for(auto it: nodes)
nex[tip[it]].push_back(it);
for(auto it: nodes)
mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0;
int nn = cnt;
for(int i = 1; i <= nn; ++i)
centroidDecomp(nex[i]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q;
ll w;
cin >> n >> q >> w;
vector<tuple<int, int, ll> > Muchie;
for(int i = 1; i < n; ++i)
{
int a, b;
ll c;
cin >> a >> b >> c;
Muchie.push_back(make_tuple(min(a, b), max(a, b), c));
G[a].push_back({b, c});
G[b].push_back({a, c});
}
vector<int> noduri;
for(int i = 1; i <= n; ++i)
noduri.push_back(i);
centroidDecomp(noduri);
auto calc = [](int i)
{
vector<ll> vec;
for(auto it: frati[i])
{
ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
vec.push_back(val);
}
sort(vec.begin(), vec.end(), greater<ll>());
ll maxxx = 0;
if(vec.size() > 1)
maxxx = vec[0] + vec[1];
else maxxx = vec[0];
return maxxx;
};
multiset<ll> s;
for(int i = 1; i <= n; ++i)
if(frati[i].size())
maxx[i] = calc(i), s.insert(-maxx[i]);
ll last = 0;
for(int i = 1; i <= q; ++i)
{
int d;
ll e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
int x, y;
ll c;
tie(x, y, c) = Muchie[d];
for(auto it: mp[ {x, y}]){
interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c);
s.erase(s.find(-maxx[it.second]));
maxx[it.second] = calc(it.second);
s.insert(-maxx[it.second]);
}
Muchie[d] = make_tuple(x, y, e);
cout << -*s.begin() << '\n';
last = -*s.begin();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<int> frati[NMAX];
map<pair<int, int>, vector<pair<int, int> > > mp;
bool dead[NMAX], mark[NMAX], viz[NMAX];
int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
ll dist[NMAX], maxx[NMAX];
struct SEGTREE
{
vector<ll> Arb, lazy;
vector<int> in, out;
int cati;
inline void init(int n)
{
cati = n;
int put = 1;
while(put <= n)
put <<= 1;
put <<= 1;
Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put << 1);
}
inline void build(int nod, int st, int dr)
{
if(st == dr)
{
Arb[nod] = dist[st];
return;
}
int mij = (st + dr) / 2;
build(2 * nod, st, mij);
build(2 * nod + 1, mij + 1, dr);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline void push(int nod){
if(lazy[nod]){
Arb[nod] += lazy[nod];
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
lazy[nod] = 0;
}
}
inline void update(int nod, int st, int dr, int a, int b, ll val){
if(a <= st && dr <= b){
lazy[nod] += val;
push(nod);
return;
}
push(nod);
int mij = (st + dr) / 2;
if(a <= mij)
update(2 * nod, st, mij, a, b, val);
if(b > mij)
update(2 * nod + 1, mij + 1, dr, a, b, val);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline ll query(int nod, int st, int dr, int a, int b){
push(nod);
if(a <= st && dr <= b)
return Arb[nod];
int mij = (st + dr) / 2;
ll rez1 = 0, rez2 = 0;
if(a <= mij)
rez1 = query(2 * nod, st, mij, a, b);
if(b > mij)
rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
return max(rez1, rez2);
}
} interv[NMAX];
inline int getC(int nod)
{
viz[nod] = 1;
sz[nod] = 1;
int maxx = 0;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
{
int c = getC(it.first);
if(c != -1)
return c;
sz[nod] += sz[it.first];
maxx = max(maxx, sz[it.first]);
}
maxx = max(maxx, dim - sz[nod]);
if(maxx <= dim / 2)
return nod;
return -1;
}
inline void DFS(int nod)
{
viz[nod] = 1;
tip[nod] = cnt;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
DFS(it.first);
}
inline void buildTree(int nod, int tata = -1)
{
interv[baza].in[id[nod]] = ++mov;
for(auto it: G[nod])
if(tata != it.first && mark[it.first])
{
mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza});
dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second;
buildTree(it.first, nod);
}
interv[baza].out[id[nod]] = mov;
}
inline void centroidDecomp(vector<int> nodes)
{
if(nodes.size() == 1)
return;
int mr = 0;
for(auto it: nodes)
mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr;
dim = nodes.size();
int cen = getC(nodes[0]);
baza = cen;
mov = dist[1] = 0;
interv[baza].init(nodes.size());
buildTree(cen);
interv[baza].build(1, 1, nodes.size());
for(auto it: nodes)
viz[it] = 0;
viz[cen] = 1;
cnt = 0;
for(auto it: G[cen])
if(!viz[it.first] && mark[it.first])
{
frati[cen].push_back(id[it.first]);
++cnt;
DFS(it.first);
}
vector<vector<int> > nex(cnt + 1);
for(auto it: nodes)
nex[tip[it]].push_back(it);
for(auto it: nodes)
mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0;
int nn = cnt;
for(int i = 1; i <= nn; ++i)
centroidDecomp(nex[i]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q;
ll w;
cin >> n >> q >> w;
vector<tuple<int, int, ll> > Muchie;
for(int i = 1; i < n; ++i)
{
int a, b;
ll c;
cin >> a >> b >> c;
Muchie.push_back(make_tuple(min(a, b), max(a, b), c));
G[a].push_back({b, c});
G[b].push_back({a, c});
}
vector<int> noduri;
for(int i = 1; i <= n; ++i)
noduri.push_back(i);
centroidDecomp(noduri);
auto calc = [](int i)
{
vector<ll> vec;
for(auto it: frati[i])
{
ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
vec.push_back(val);
}
sort(vec.begin(), vec.end(), greater<ll>());
ll maxxx = 0;
if(vec.size() > 1)
maxxx = vec[0] + vec[1];
else maxxx = vec[0];
return maxxx;
};
multiset<ll> s;
for(int i = 1; i <= n; ++i)
if(frati[i].size())
maxx[i] = calc(i), s.insert(-maxx[i]);
ll last = 0;
for(int i = 1; i <= q; ++i)
{
int d;
ll e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
int x, y;
ll c;
tie(x, y, c) = Muchie[d];
for(auto it: mp[ {x, y}]){
interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c);
s.erase(s.find(-maxx[it.second]));
maxx[it.second] = calc(it.second);
s.insert(-maxx[it.second]);
}
Muchie[d] = make_tuple(x, y, e);
cout << -*s.begin() << '\n';
last = -*s.begin();
}
return 0;
}
Compilation message
diameter.cpp:230:11: error: redefinition of 'const int NMAX'
230 | const int NMAX(100005);
| ^~~~
diameter.cpp:6:11: note: 'const int NMAX' previously defined here
6 | const int NMAX(100005);
| ^~~~
diameter.cpp:231:24: error: redefinition of 'std::vector<std::pair<int, long long int> > G [100005]'
231 | vector<pair<int, ll> > G[NMAX];
| ^
diameter.cpp:7:24: note: 'std::vector<std::pair<int, long long int> > G [100005]' previously declared here
7 | vector<pair<int, ll> > G[NMAX];
| ^
diameter.cpp:232:13: error: redefinition of 'std::vector<int> frati [100005]'
232 | vector<int> frati[NMAX];
| ^~~~~
diameter.cpp:8:13: note: 'std::vector<int> frati [100005]' previously declared here
8 | vector<int> frati[NMAX];
| ^~~~~
diameter.cpp:233:47: error: redefinition of 'std::map<std::pair<int, int>, std::vector<std::pair<int, int> > > mp'
233 | map<pair<int, int>, vector<pair<int, int> > > mp;
| ^~
diameter.cpp:9:47: note: 'std::map<std::pair<int, int>, std::vector<std::pair<int, int> > > mp' previously declared here
9 | map<pair<int, int>, vector<pair<int, int> > > mp;
| ^~
diameter.cpp:234:6: error: redefinition of 'bool dead [100005]'
234 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~~
diameter.cpp:10:6: note: 'bool dead [100005]' previously declared here
10 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~~
diameter.cpp:234:18: error: redefinition of 'bool mark [100005]'
234 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~~
diameter.cpp:10:18: note: 'bool mark [100005]' previously declared here
10 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~~
diameter.cpp:234:30: error: redefinition of 'bool viz [100005]'
234 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~
diameter.cpp:10:30: note: 'bool viz [100005]' previously declared here
10 | bool dead[NMAX], mark[NMAX], viz[NMAX];
| ^~~
diameter.cpp:235:5: error: redefinition of 'int pas'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:11:5: note: 'int pas' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:235:10: error: redefinition of 'int dim'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:11:10: note: 'int dim' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:235:15: error: redefinition of 'int sz [100005]'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~
diameter.cpp:11:15: note: 'int sz [100005]' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~
diameter.cpp:235:25: error: redefinition of 'int tip [100005]'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:11:25: note: 'int tip [100005]' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:235:36: error: redefinition of 'int cnt'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:11:36: note: 'int cnt' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:235:41: error: redefinition of 'int baza'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~~
diameter.cpp:11:41: note: 'int baza' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~~
diameter.cpp:235:47: error: redefinition of 'int mov'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:11:47: note: 'int mov' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~~
diameter.cpp:235:52: error: redefinition of 'int id [100005]'
235 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~
diameter.cpp:11:52: note: 'int id [100005]' previously declared here
11 | int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
| ^~
diameter.cpp:236:4: error: redefinition of 'll dist [100005]'
236 | ll dist[NMAX], maxx[NMAX];
| ^~~~
diameter.cpp:12:4: note: 'll dist [100005]' previously declared here
12 | ll dist[NMAX], maxx[NMAX];
| ^~~~
diameter.cpp:236:16: error: redefinition of 'll maxx [100005]'
236 | ll dist[NMAX], maxx[NMAX];
| ^~~~
diameter.cpp:12:16: note: 'll maxx [100005]' previously declared here
12 | ll dist[NMAX], maxx[NMAX];
| ^~~~
diameter.cpp:238:8: error: redefinition of 'struct SEGTREE'
238 | struct SEGTREE
| ^~~~~~~
diameter.cpp:14:8: note: previous definition of 'struct SEGTREE'
14 | struct SEGTREE
| ^~~~~~~
diameter.cpp:298:3: error: conflicting declaration 'int interv [100005]'
298 | } interv[NMAX];
| ^~~~~~
diameter.cpp:74:3: note: previous declaration as 'SEGTREE interv [100005]'
74 | } interv[NMAX];
| ^~~~~~
diameter.cpp:300:12: error: redefinition of 'int getC(int)'
300 | inline int getC(int nod)
| ^~~~
diameter.cpp:76:12: note: 'int getC(int)' previously defined here
76 | inline int getC(int nod)
| ^~~~
diameter.cpp:320:13: error: redefinition of 'void DFS(int)'
320 | inline void DFS(int nod)
| ^~~
diameter.cpp:96:13: note: 'void DFS(int)' previously defined here
96 | inline void DFS(int nod)
| ^~~
diameter.cpp:329:13: error: redefinition of 'void buildTree(int, int)'
329 | inline void buildTree(int nod, int tata = -1)
| ^~~~~~~~~
diameter.cpp:105:13: note: 'void buildTree(int, int)' previously defined here
105 | inline void buildTree(int nod, int tata = -1)
| ^~~~~~~~~
diameter.cpp:342:13: error: redefinition of 'void centroidDecomp(std::vector<int>)'
342 | inline void centroidDecomp(vector<int> nodes)
| ^~~~~~~~~~~~~~
diameter.cpp:118:13: note: 'void centroidDecomp(std::vector<int>)' previously defined here
118 | inline void centroidDecomp(vector<int> nodes)
| ^~~~~~~~~~~~~~
diameter.cpp:380:5: error: redefinition of 'int main()'
380 | int main()
| ^~~~
diameter.cpp:156:5: note: 'int main()' previously defined here
156 | int main()
| ^~~~
