#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];
multiset<ll> vec[NMAX];
map<int, ll> cum[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);
push(2 * nod), push(2 * nod + 1);
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, bool da)
{
if(da)
{
for(auto it: frati[i])
{
ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
vec[i].insert(val);
cum[i][it] = val;
}
}
auto it = vec[i].rbegin();
ll rz = *it;
if(vec[i].size() >= 2)
{
--it;
rz += *it;
}
return rz;
};
multiset<ll> s;
for(int i = 1; i <= n; ++i)
if(frati[i].size())
maxx[i] = calc(i, 1), 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);
for(auto careF: frati[it.second])
if(interv[it.second].in[careF] <= interv[it.second].in[it.first] && interv[it.second].in[it.first] <= interv[it.second].out[careF])
{
ll newV = interv[it.second].query(1, 1, interv[it.second].cati, interv[it.second].in[careF], interv[it.second].out[careF]);
vec[it.second].erase(vec[it.second].find(cum[it.second][careF]));
vec[it.second].insert(newV);
cum[it.second][careF] = newV;
break;
}
s.erase(s.find(-maxx[it.second]));
maxx[it.second] = calc(it.second, 0);
s.insert(-maxx[it.second]);
}
Muchie[d] = make_tuple(x, y, e);
cout << -*s.begin() << '\n';
last = -*s.begin();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
25484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2806 ms |
171400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
