#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() {
ll a=top(), b=0;
if (pq.size()) {
int last=pq.top().second;
while(1) {
norm();
if (pq.size()&&pq.top().second==last)
pq.pop();
else
break;
}
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)
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
20692 KB |
Output is correct |
2 |
Correct |
10 ms |
20628 KB |
Output is correct |
3 |
Correct |
10 ms |
20684 KB |
Output is correct |
4 |
Correct |
11 ms |
20700 KB |
Output is correct |
5 |
Correct |
10 ms |
20688 KB |
Output is correct |
6 |
Correct |
11 ms |
20692 KB |
Output is correct |
7 |
Correct |
11 ms |
20684 KB |
Output is correct |
8 |
Correct |
10 ms |
20692 KB |
Output is correct |
9 |
Correct |
10 ms |
20692 KB |
Output is correct |
10 |
Correct |
11 ms |
20692 KB |
Output is correct |
11 |
Correct |
10 ms |
20660 KB |
Output is correct |
12 |
Correct |
11 ms |
20740 KB |
Output is correct |
13 |
Correct |
10 ms |
20768 KB |
Output is correct |
14 |
Correct |
11 ms |
20692 KB |
Output is correct |
15 |
Correct |
10 ms |
20784 KB |
Output is correct |
16 |
Correct |
11 ms |
20692 KB |
Output is correct |
17 |
Correct |
11 ms |
20736 KB |
Output is correct |
18 |
Correct |
11 ms |
20692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
20692 KB |
Output is correct |
2 |
Correct |
10 ms |
20628 KB |
Output is correct |
3 |
Correct |
10 ms |
20684 KB |
Output is correct |
4 |
Correct |
11 ms |
20700 KB |
Output is correct |
5 |
Correct |
10 ms |
20688 KB |
Output is correct |
6 |
Correct |
11 ms |
20692 KB |
Output is correct |
7 |
Correct |
11 ms |
20684 KB |
Output is correct |
8 |
Correct |
10 ms |
20692 KB |
Output is correct |
9 |
Correct |
10 ms |
20692 KB |
Output is correct |
10 |
Correct |
11 ms |
20692 KB |
Output is correct |
11 |
Correct |
10 ms |
20660 KB |
Output is correct |
12 |
Correct |
11 ms |
20740 KB |
Output is correct |
13 |
Correct |
10 ms |
20768 KB |
Output is correct |
14 |
Correct |
11 ms |
20692 KB |
Output is correct |
15 |
Correct |
10 ms |
20784 KB |
Output is correct |
16 |
Correct |
11 ms |
20692 KB |
Output is correct |
17 |
Correct |
11 ms |
20736 KB |
Output is correct |
18 |
Correct |
11 ms |
20692 KB |
Output is correct |
19 |
Correct |
29 ms |
21756 KB |
Output is correct |
20 |
Correct |
26 ms |
21844 KB |
Output is correct |
21 |
Correct |
32 ms |
21940 KB |
Output is correct |
22 |
Correct |
27 ms |
22400 KB |
Output is correct |
23 |
Correct |
41 ms |
24908 KB |
Output is correct |
24 |
Correct |
49 ms |
26224 KB |
Output is correct |
25 |
Correct |
51 ms |
27324 KB |
Output is correct |
26 |
Correct |
51 ms |
28140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
20692 KB |
Output is correct |
2 |
Correct |
13 ms |
20660 KB |
Output is correct |
3 |
Correct |
13 ms |
20676 KB |
Output is correct |
4 |
Correct |
22 ms |
20948 KB |
Output is correct |
5 |
Correct |
69 ms |
22180 KB |
Output is correct |
6 |
Correct |
10 ms |
20692 KB |
Output is correct |
7 |
Correct |
11 ms |
20816 KB |
Output is correct |
8 |
Correct |
11 ms |
20868 KB |
Output is correct |
9 |
Correct |
13 ms |
20948 KB |
Output is correct |
10 |
Correct |
25 ms |
21468 KB |
Output is correct |
11 |
Correct |
85 ms |
23156 KB |
Output is correct |
12 |
Correct |
17 ms |
22452 KB |
Output is correct |
13 |
Correct |
16 ms |
22484 KB |
Output is correct |
14 |
Correct |
16 ms |
22612 KB |
Output is correct |
15 |
Correct |
32 ms |
22900 KB |
Output is correct |
16 |
Correct |
99 ms |
24636 KB |
Output is correct |
17 |
Correct |
84 ms |
55968 KB |
Output is correct |
18 |
Correct |
92 ms |
56016 KB |
Output is correct |
19 |
Correct |
101 ms |
56096 KB |
Output is correct |
20 |
Correct |
108 ms |
56168 KB |
Output is correct |
21 |
Correct |
216 ms |
59300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
21588 KB |
Output is correct |
2 |
Correct |
37 ms |
22260 KB |
Output is correct |
3 |
Correct |
132 ms |
24316 KB |
Output is correct |
4 |
Correct |
300 ms |
26868 KB |
Output is correct |
5 |
Correct |
36 ms |
32876 KB |
Output is correct |
6 |
Correct |
70 ms |
33732 KB |
Output is correct |
7 |
Correct |
243 ms |
37752 KB |
Output is correct |
8 |
Correct |
460 ms |
42844 KB |
Output is correct |
9 |
Correct |
145 ms |
88632 KB |
Output is correct |
10 |
Correct |
208 ms |
89540 KB |
Output is correct |
11 |
Correct |
467 ms |
93028 KB |
Output is correct |
12 |
Correct |
766 ms |
98024 KB |
Output is correct |
13 |
Correct |
273 ms |
163124 KB |
Output is correct |
14 |
Correct |
347 ms |
164744 KB |
Output is correct |
15 |
Correct |
730 ms |
170408 KB |
Output is correct |
16 |
Correct |
1022 ms |
171988 KB |
Output is correct |
17 |
Correct |
1623 ms |
206020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1703 ms |
155516 KB |
Output is correct |
2 |
Correct |
1804 ms |
163000 KB |
Output is correct |
3 |
Correct |
1820 ms |
162732 KB |
Output is correct |
4 |
Correct |
1744 ms |
162892 KB |
Output is correct |
5 |
Correct |
1678 ms |
157076 KB |
Output is correct |
6 |
Correct |
1484 ms |
138420 KB |
Output is correct |
7 |
Correct |
2209 ms |
202820 KB |
Output is correct |
8 |
Correct |
2191 ms |
202868 KB |
Output is correct |
9 |
Correct |
2179 ms |
202812 KB |
Output is correct |
10 |
Correct |
2238 ms |
202080 KB |
Output is correct |
11 |
Correct |
2154 ms |
193680 KB |
Output is correct |
12 |
Correct |
1864 ms |
150276 KB |
Output is correct |
13 |
Correct |
2078 ms |
214800 KB |
Output is correct |
14 |
Correct |
2005 ms |
214868 KB |
Output is correct |
15 |
Correct |
2017 ms |
214848 KB |
Output is correct |
16 |
Correct |
2110 ms |
214388 KB |
Output is correct |
17 |
Correct |
2019 ms |
205444 KB |
Output is correct |
18 |
Correct |
1689 ms |
156124 KB |
Output is correct |
19 |
Correct |
2118 ms |
214748 KB |
Output is correct |
20 |
Correct |
2082 ms |
214756 KB |
Output is correct |
21 |
Correct |
2085 ms |
214792 KB |
Output is correct |
22 |
Correct |
2114 ms |
214140 KB |
Output is correct |
23 |
Correct |
2013 ms |
205220 KB |
Output is correct |
24 |
Correct |
1756 ms |
155972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
20692 KB |
Output is correct |
2 |
Correct |
10 ms |
20628 KB |
Output is correct |
3 |
Correct |
10 ms |
20684 KB |
Output is correct |
4 |
Correct |
11 ms |
20700 KB |
Output is correct |
5 |
Correct |
10 ms |
20688 KB |
Output is correct |
6 |
Correct |
11 ms |
20692 KB |
Output is correct |
7 |
Correct |
11 ms |
20684 KB |
Output is correct |
8 |
Correct |
10 ms |
20692 KB |
Output is correct |
9 |
Correct |
10 ms |
20692 KB |
Output is correct |
10 |
Correct |
11 ms |
20692 KB |
Output is correct |
11 |
Correct |
10 ms |
20660 KB |
Output is correct |
12 |
Correct |
11 ms |
20740 KB |
Output is correct |
13 |
Correct |
10 ms |
20768 KB |
Output is correct |
14 |
Correct |
11 ms |
20692 KB |
Output is correct |
15 |
Correct |
10 ms |
20784 KB |
Output is correct |
16 |
Correct |
11 ms |
20692 KB |
Output is correct |
17 |
Correct |
11 ms |
20736 KB |
Output is correct |
18 |
Correct |
11 ms |
20692 KB |
Output is correct |
19 |
Correct |
29 ms |
21756 KB |
Output is correct |
20 |
Correct |
26 ms |
21844 KB |
Output is correct |
21 |
Correct |
32 ms |
21940 KB |
Output is correct |
22 |
Correct |
27 ms |
22400 KB |
Output is correct |
23 |
Correct |
41 ms |
24908 KB |
Output is correct |
24 |
Correct |
49 ms |
26224 KB |
Output is correct |
25 |
Correct |
51 ms |
27324 KB |
Output is correct |
26 |
Correct |
51 ms |
28140 KB |
Output is correct |
27 |
Correct |
11 ms |
20692 KB |
Output is correct |
28 |
Correct |
13 ms |
20660 KB |
Output is correct |
29 |
Correct |
13 ms |
20676 KB |
Output is correct |
30 |
Correct |
22 ms |
20948 KB |
Output is correct |
31 |
Correct |
69 ms |
22180 KB |
Output is correct |
32 |
Correct |
10 ms |
20692 KB |
Output is correct |
33 |
Correct |
11 ms |
20816 KB |
Output is correct |
34 |
Correct |
11 ms |
20868 KB |
Output is correct |
35 |
Correct |
13 ms |
20948 KB |
Output is correct |
36 |
Correct |
25 ms |
21468 KB |
Output is correct |
37 |
Correct |
85 ms |
23156 KB |
Output is correct |
38 |
Correct |
17 ms |
22452 KB |
Output is correct |
39 |
Correct |
16 ms |
22484 KB |
Output is correct |
40 |
Correct |
16 ms |
22612 KB |
Output is correct |
41 |
Correct |
32 ms |
22900 KB |
Output is correct |
42 |
Correct |
99 ms |
24636 KB |
Output is correct |
43 |
Correct |
84 ms |
55968 KB |
Output is correct |
44 |
Correct |
92 ms |
56016 KB |
Output is correct |
45 |
Correct |
101 ms |
56096 KB |
Output is correct |
46 |
Correct |
108 ms |
56168 KB |
Output is correct |
47 |
Correct |
216 ms |
59300 KB |
Output is correct |
48 |
Correct |
16 ms |
21588 KB |
Output is correct |
49 |
Correct |
37 ms |
22260 KB |
Output is correct |
50 |
Correct |
132 ms |
24316 KB |
Output is correct |
51 |
Correct |
300 ms |
26868 KB |
Output is correct |
52 |
Correct |
36 ms |
32876 KB |
Output is correct |
53 |
Correct |
70 ms |
33732 KB |
Output is correct |
54 |
Correct |
243 ms |
37752 KB |
Output is correct |
55 |
Correct |
460 ms |
42844 KB |
Output is correct |
56 |
Correct |
145 ms |
88632 KB |
Output is correct |
57 |
Correct |
208 ms |
89540 KB |
Output is correct |
58 |
Correct |
467 ms |
93028 KB |
Output is correct |
59 |
Correct |
766 ms |
98024 KB |
Output is correct |
60 |
Correct |
273 ms |
163124 KB |
Output is correct |
61 |
Correct |
347 ms |
164744 KB |
Output is correct |
62 |
Correct |
730 ms |
170408 KB |
Output is correct |
63 |
Correct |
1022 ms |
171988 KB |
Output is correct |
64 |
Correct |
1623 ms |
206020 KB |
Output is correct |
65 |
Correct |
1703 ms |
155516 KB |
Output is correct |
66 |
Correct |
1804 ms |
163000 KB |
Output is correct |
67 |
Correct |
1820 ms |
162732 KB |
Output is correct |
68 |
Correct |
1744 ms |
162892 KB |
Output is correct |
69 |
Correct |
1678 ms |
157076 KB |
Output is correct |
70 |
Correct |
1484 ms |
138420 KB |
Output is correct |
71 |
Correct |
2209 ms |
202820 KB |
Output is correct |
72 |
Correct |
2191 ms |
202868 KB |
Output is correct |
73 |
Correct |
2179 ms |
202812 KB |
Output is correct |
74 |
Correct |
2238 ms |
202080 KB |
Output is correct |
75 |
Correct |
2154 ms |
193680 KB |
Output is correct |
76 |
Correct |
1864 ms |
150276 KB |
Output is correct |
77 |
Correct |
2078 ms |
214800 KB |
Output is correct |
78 |
Correct |
2005 ms |
214868 KB |
Output is correct |
79 |
Correct |
2017 ms |
214848 KB |
Output is correct |
80 |
Correct |
2110 ms |
214388 KB |
Output is correct |
81 |
Correct |
2019 ms |
205444 KB |
Output is correct |
82 |
Correct |
1689 ms |
156124 KB |
Output is correct |
83 |
Correct |
2118 ms |
214748 KB |
Output is correct |
84 |
Correct |
2082 ms |
214756 KB |
Output is correct |
85 |
Correct |
2085 ms |
214792 KB |
Output is correct |
86 |
Correct |
2114 ms |
214140 KB |
Output is correct |
87 |
Correct |
2013 ms |
205220 KB |
Output is correct |
88 |
Correct |
1756 ms |
155972 KB |
Output is correct |
89 |
Correct |
1668 ms |
160720 KB |
Output is correct |
90 |
Correct |
1889 ms |
187148 KB |
Output is correct |
91 |
Correct |
2177 ms |
198432 KB |
Output is correct |
92 |
Correct |
2220 ms |
202000 KB |
Output is correct |
93 |
Correct |
2249 ms |
206644 KB |
Output is correct |
94 |
Correct |
2185 ms |
210456 KB |
Output is correct |
95 |
Correct |
2062 ms |
214532 KB |
Output is correct |
96 |
Correct |
2041 ms |
214268 KB |
Output is correct |
97 |
Correct |
2057 ms |
214252 KB |
Output is correct |
98 |
Correct |
2051 ms |
214264 KB |
Output is correct |
99 |
Correct |
2170 ms |
214404 KB |
Output is correct |
100 |
Correct |
2033 ms |
214324 KB |
Output is correct |