#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
struct seg_tree {
int n;
vector<ll> st, lz;
seg_tree() {}
seg_tree(int n) : n(n) {
st.resize(4*n);
lz.resize(4*n);
}
void init(vector<ll>& a) {
assert(a.size()==n);
bld(1, 0, n-1, a);
}
void bld(int u, int l, int r, vector<ll>& a) {
if (l==r) {
st[u]=a[l];
return;
}
int mid=(l+r)/2;
bld(2*u, l, mid, a);
bld(2*u+1, mid+1, r, a);
st[u]=max(st[2*u], st[2*u+1]);
}
void psh(int u, int l, int r) {
if (lz[u]) {
st[u]+=lz[u];
if (l!=r)
lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
lz[u]=0;
}
}
void upd(int ql, int qr, ll x, int u, int l, int r) {
psh(u, l, r);
if (l>qr||r<ql)
return;
if (ql<=l&&r<=qr) {
lz[u]+=x;
psh(u, l, r);
return;
}
int mid=(l+r)/2;
upd(ql, qr, x, 2*u, l, mid);
upd(ql, qr, x, 2*u+1, mid+1, r);
st[u]=max(st[2*u], st[2*u+1]);
}
void upd(int ql, int qr, ll x) {
upd(ql, qr, x, 1, 0, n-1);
}
ll qry(int ql, int qr, int u, int l, int r) {
psh(u, l, r);
if (l>qr||r<ql)
return 0;
if (ql<=l&&r<=qr)
return st[u];
int mid=(l+r)/2;
return max(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}
ll qry(int ql, int qr) {
return qry(ql, qr, 1, 0, n-1);
}
};
struct PQ {
vector<ll> d;
priority_queue<pair<ll, int>> pq;
PQ() {}
PQ(vector<ll> d) : d(d) {
for (int i=0; i<d.size(); ++i)
push(i);
}
void push(int i) {
pq.emplace(d[i], i);
}
void upd(int i, ll x) {
pq.emplace(d[i]=x, i);
}
void norm() {
while(pq.size()&&pq.top().first!=d[pq.top().second])
pq.pop();
}
ll top() {
norm();
return pq.size()?pq.top().first:0;
}
ll diam() {
norm();
ll a=top(), b=0;
if (pq.size()) {
int last=pq.top().second;
pq.pop();
norm();
b=top();
push(last);
}
return a+b;
}
};
const int mxN=1e5;
int n, q, eu[mxN], ev[mxN], s[mxN], tin[mxN], t;
ll wlim, ew[mxN];
vector<int> adj[mxN], child_tin[mxN], child_tout[mxN];
bool dead[mxN];
vector<ll> init_dist, init_diam;
vector<ar<int, 4>> by_edge[mxN]; // which trees is this edge on, {tree, tree_child, tin, tout}
seg_tree st[mxN];
PQ best_children[mxN], ans;
int dfs1(int u, int p) { // get size
s[u]=1;
for (int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if (v!=p&&!dead[v])
s[u]+=dfs1(v, u);
}
return s[u];
}
int get_centroid(int u) {
int ts=dfs1(u, -1);
bool ok=1;
while(ok) {
ok=0;
for (int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if (s[v]<s[u]&&!dead[v]&&s[v]>ts/2) {
ok=1;
u=v;
break;
}
}
}
return u;
}
int rt, rt_child;
void dfs2(int u, int p, ll d) {
tin[u]=t++;
init_dist.push_back(d);
for (int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if (v!=p&&!dead[v]) {
dfs2(v, u, d+ew[e]);
by_edge[e].push_back({rt, rt_child, tin[v], t-1});
if (p==-1) {
child_tin[rt].push_back(tin[v]);
child_tout[rt].push_back(t-1);
++rt_child;
}
}
}
}
void solve(int u=0) {
//cout << u << endl;
u=get_centroid(u);
dead[u]=1;
//cout << u << endl;
t=0, rt=u, rt_child=0;
init_dist.clear();
dfs2(u, -1, 0);
//cout << u << endl;
st[u]=seg_tree(t);
st[u].init(init_dist);
//cout << u << " " << t << endl;
vector<ll> init_best;
for (int i=0; i<rt_child; ++i)
init_best.push_back(st[u].qry(child_tin[u][i], child_tout[u][i]));
//cout << u << endl;
best_children[u]=PQ(init_best);
init_diam[u]=best_children[u].diam();
for (int e : adj[u])
if (!dead[eu[e]^ev[e]^u])
solve(eu[e]^ev[e]^u);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> wlim;
for (int i=0; i<n-1; ++i) {
cin >> eu[i] >> ev[i] >> ew[i], --eu[i], --ev[i];
adj[eu[i]].push_back(i);
adj[ev[i]].push_back(i);
}
init_diam.resize(n);
solve();
ans=PQ(init_diam);
ll last=0;
while(q--) {
int i;
ll nxt;
cin >> i >> nxt;
i=(i+last)%(n-1);
nxt=(nxt+last)%wlim;
//cout << i << " " << nxt << endl;
ll change=nxt-ew[i];
for (auto [u, x, a, b] : by_edge[i]) {
//cout << u << " " << x << " " << a << " " << b << endl;
st[u].upd(a, b, change);
best_children[u].upd(x, st[u].qry(child_tin[u][x], child_tout[u][x]));
ans.upd(u, best_children[u].diam());
}
ew[i]=nxt;
cout << (last=ans.top()) << "\n";
}
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from diameter.cpp:1:
diameter.cpp: In member function 'void seg_tree::init(std::vector<long long int>&)':
diameter.cpp:16:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
16 | assert(a.size()==n);
| ~~~~~~~~^~~
diameter.cpp: In constructor 'PQ::PQ(std::vector<long long int>)':
diameter.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0; i<d.size(); ++i)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
20624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
20624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20684 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20688 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
20696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
21808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1675 ms |
164104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
20624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
