#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
const int maxn = 1e5 + 3;
vector<pair<int,int> > adj[maxn],edges;
vector<int> partOf[maxn];
vector<ll> seg[maxn],lazy[maxn];
bool isCent[maxn];
int subSz[maxn],centRoot,timer[maxn];
unordered_map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn];
set<pair<int,ll> > bestEdge[maxn],result;
ll cost[maxn];
void dfsSz(int u,int p){
subSz[u] = 1;
for(auto [v,w] : adj[u]){
if(v != p && !isCent[v]){
dfsSz(v,u);
subSz[u] += subSz[v];
}
}
}
int fnCent(int u,int p,int s){
for(auto [v,w] : adj[u]){
if(v != p && !isCent[v] && subSz[v] > s/2){
return fnCent(v,u,s);
}
}
return u;
}
void dfsTour(int c,int u,int p){
for(auto [v,w] : adj[u]){
if(v != p && !isCent[v]){
partOf[w].emplace_back(c);
tin[c][w] = timer[c]++;
dfsTour(c,v,u);
tout[c][w] = timer[c]++;
}
}
}
void dfsEdgeRoot(int c,int d,int u,int p){
for(auto [v,w] : adj[u]){
if(v != p && !isCent[v]){
edgeRoot[c][w] = d;
dfsEdgeRoot(c,d,v,u);
}
}
}
void dfsCent(int u,int p){
dfsSz(u,p);
int cent = fnCent(u,u,subSz[u]);
isCent[cent] = true;
if(p != -1){
centRoot = cent;
}
dfsTour(cent,cent,cent);
for(auto [v,w] : adj[cent]){
if(!isCent[v]){
bestEdge[cent].emplace(0,w);
edgeRoot[cent][w] = w;
dfsEdgeRoot(cent,w,v,cent);
}
}
seg[cent].resize(4*timer[cent]);
lazy[cent].resize(4*timer[cent]);
for(auto [v,w] : adj[cent]){
if(!isCent[v]){
dfsCent(v,cent);
}
}
}
// Segment Tree + Lazy Propagation
void push(int c,int i){
lazy[c][i<<1] += lazy[c][i];
seg[c][i<<1] += lazy[c][i];
lazy[c][i<<1|1] += lazy[c][i];
seg[c][i<<1|1] += lazy[c][i];
lazy[c][i] = 0;
}
void upd(int c,int i,int l,int r,int ul,int ur,ll v){
if(ul <= l && r <= ur){
seg[c][i] += v;
lazy[c][i] += v;
}else if(ul > r || ur < l){
return;
}else{
int m = (l+r)/2;
push(c,i);
upd(c,i<<1,l,m,ul,ur,v);
upd(c,i<<1|1,m+1,r,ul,ur,v);
seg[c][i] = max(seg[c][i<<1],seg[c][i<<1|1]);
}
}
ll qry(int c,int i,int l,int r,int ql,int qr){
if(ql <= l && r <= qr){
return seg[c][i];
}else if(ql > r || qr < l){
return 0;
}else{
int m = (l+r)/2;
push(c,i);
return max(qry(c,i<<1,l,m,ql,qr),qry(c,i<<1|1,m+1,r,ql,qr));
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
ll w;
cin >> n >> q >> w;
for(int i=1;i<n;i++){
int u,v;
ll w;
cin >> u >> v >> w;
u--; v--;
adj[u].emplace_back(v,i);
adj[v].emplace_back(u,i);
edges.emplace_back(u,v);
cost[i] = w;
}
dfsCent(0,-1);
for(int i=1;i<n;i++){
for(int it : partOf[i]){
bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])));
upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,cost[i]);
upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-cost[i]);
bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]));
}
}
for(int i=0;i<n;i++){
if(bestEdge[i].size() > 1){
result.emplace((*prev(bestEdge[i].end())).first+(*prev(prev(bestEdge[i].end()))).first,i);
}else if(bestEdge[i].size()){
result.emplace((*prev(bestEdge[i].end())).first,i);
}else{
result.emplace(0,i);
}
}
ll last = 0;
while(q--){
int i;
ll j;
cin >> i >> j;
i = (i+last)%(n-1)+1;
j = (j+last)%w;
ll df = j-cost[i];
for(int it : partOf[i]){
if(bestEdge[it].size() > 1){
result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it)));
}else if(bestEdge[it].size()){
result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first,it)));
}else{
result.erase(result.find(make_pair(0,it)));
}
bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])));
upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,df);
upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-df);
bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]));
if(bestEdge[it].size() > 1){
result.emplace((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it);
}else if(bestEdge[it].size()){
result.emplace((*prev(bestEdge[it].end())).first,it);
}else{
result.emplace(0,it);
}
}
cost[i] = j;
last = (*prev(result.end())).first;
cout << (*prev(result.end())).first << "\n";
}
}
Compilation message
diameter.cpp: In function 'void dfsSz(int, int)':
diameter.cpp:19:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'int fnCent(int, int, int)':
diameter.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsTour(int, int, int)':
diameter.cpp:35:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsEdgeRoot(int, int, int, int)':
diameter.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsCent(int, int)':
diameter.cpp:60:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for(auto [v,w] : adj[cent]){
| ^
diameter.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
69 | for(auto [v,w] : adj[cent]){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
30880 KB |
Output is correct |
2 |
Correct |
18 ms |
30864 KB |
Output is correct |
3 |
Correct |
16 ms |
30876 KB |
Output is correct |
4 |
Correct |
18 ms |
30832 KB |
Output is correct |
5 |
Correct |
18 ms |
30808 KB |
Output is correct |
6 |
Correct |
17 ms |
30860 KB |
Output is correct |
7 |
Correct |
18 ms |
30804 KB |
Output is correct |
8 |
Correct |
18 ms |
30804 KB |
Output is correct |
9 |
Correct |
19 ms |
30896 KB |
Output is correct |
10 |
Correct |
18 ms |
30804 KB |
Output is correct |
11 |
Correct |
17 ms |
30896 KB |
Output is correct |
12 |
Correct |
18 ms |
30864 KB |
Output is correct |
13 |
Correct |
18 ms |
30984 KB |
Output is correct |
14 |
Correct |
17 ms |
30916 KB |
Output is correct |
15 |
Correct |
17 ms |
30964 KB |
Output is correct |
16 |
Correct |
18 ms |
30932 KB |
Output is correct |
17 |
Correct |
17 ms |
30936 KB |
Output is correct |
18 |
Correct |
16 ms |
30932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
30880 KB |
Output is correct |
2 |
Correct |
18 ms |
30864 KB |
Output is correct |
3 |
Correct |
16 ms |
30876 KB |
Output is correct |
4 |
Correct |
18 ms |
30832 KB |
Output is correct |
5 |
Correct |
18 ms |
30808 KB |
Output is correct |
6 |
Correct |
17 ms |
30860 KB |
Output is correct |
7 |
Correct |
18 ms |
30804 KB |
Output is correct |
8 |
Correct |
18 ms |
30804 KB |
Output is correct |
9 |
Correct |
19 ms |
30896 KB |
Output is correct |
10 |
Correct |
18 ms |
30804 KB |
Output is correct |
11 |
Correct |
17 ms |
30896 KB |
Output is correct |
12 |
Correct |
18 ms |
30864 KB |
Output is correct |
13 |
Correct |
18 ms |
30984 KB |
Output is correct |
14 |
Correct |
17 ms |
30916 KB |
Output is correct |
15 |
Correct |
17 ms |
30964 KB |
Output is correct |
16 |
Correct |
18 ms |
30932 KB |
Output is correct |
17 |
Correct |
17 ms |
30936 KB |
Output is correct |
18 |
Correct |
16 ms |
30932 KB |
Output is correct |
19 |
Correct |
48 ms |
32484 KB |
Output is correct |
20 |
Correct |
55 ms |
32648 KB |
Output is correct |
21 |
Correct |
72 ms |
32916 KB |
Output is correct |
22 |
Correct |
62 ms |
33356 KB |
Output is correct |
23 |
Correct |
147 ms |
39940 KB |
Output is correct |
24 |
Correct |
164 ms |
42764 KB |
Output is correct |
25 |
Correct |
189 ms |
44492 KB |
Output is correct |
26 |
Correct |
212 ms |
46496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
30836 KB |
Output is correct |
2 |
Correct |
16 ms |
30864 KB |
Output is correct |
3 |
Correct |
20 ms |
30876 KB |
Output is correct |
4 |
Correct |
45 ms |
31064 KB |
Output is correct |
5 |
Correct |
95 ms |
31472 KB |
Output is correct |
6 |
Correct |
16 ms |
30804 KB |
Output is correct |
7 |
Correct |
18 ms |
31016 KB |
Output is correct |
8 |
Correct |
22 ms |
31060 KB |
Output is correct |
9 |
Correct |
19 ms |
31060 KB |
Output is correct |
10 |
Correct |
46 ms |
31264 KB |
Output is correct |
11 |
Correct |
138 ms |
31780 KB |
Output is correct |
12 |
Correct |
29 ms |
33152 KB |
Output is correct |
13 |
Correct |
26 ms |
33236 KB |
Output is correct |
14 |
Correct |
29 ms |
33248 KB |
Output is correct |
15 |
Correct |
69 ms |
33432 KB |
Output is correct |
16 |
Correct |
197 ms |
33756 KB |
Output is correct |
17 |
Correct |
288 ms |
78572 KB |
Output is correct |
18 |
Correct |
307 ms |
78492 KB |
Output is correct |
19 |
Correct |
288 ms |
78488 KB |
Output is correct |
20 |
Correct |
340 ms |
78820 KB |
Output is correct |
21 |
Correct |
648 ms |
79260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
33100 KB |
Output is correct |
2 |
Correct |
69 ms |
33108 KB |
Output is correct |
3 |
Correct |
297 ms |
33484 KB |
Output is correct |
4 |
Correct |
417 ms |
33736 KB |
Output is correct |
5 |
Correct |
176 ms |
60756 KB |
Output is correct |
6 |
Correct |
289 ms |
60988 KB |
Output is correct |
7 |
Correct |
613 ms |
61244 KB |
Output is correct |
8 |
Correct |
1045 ms |
61428 KB |
Output is correct |
9 |
Correct |
1034 ms |
210496 KB |
Output is correct |
10 |
Correct |
1140 ms |
210440 KB |
Output is correct |
11 |
Correct |
1739 ms |
210748 KB |
Output is correct |
12 |
Correct |
2556 ms |
210920 KB |
Output is correct |
13 |
Correct |
2129 ms |
414632 KB |
Output is correct |
14 |
Correct |
2376 ms |
414560 KB |
Output is correct |
15 |
Correct |
3064 ms |
414816 KB |
Output is correct |
16 |
Correct |
3919 ms |
415144 KB |
Output is correct |
17 |
Execution timed out |
5060 ms |
415064 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5077 ms |
318788 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
30880 KB |
Output is correct |
2 |
Correct |
18 ms |
30864 KB |
Output is correct |
3 |
Correct |
16 ms |
30876 KB |
Output is correct |
4 |
Correct |
18 ms |
30832 KB |
Output is correct |
5 |
Correct |
18 ms |
30808 KB |
Output is correct |
6 |
Correct |
17 ms |
30860 KB |
Output is correct |
7 |
Correct |
18 ms |
30804 KB |
Output is correct |
8 |
Correct |
18 ms |
30804 KB |
Output is correct |
9 |
Correct |
19 ms |
30896 KB |
Output is correct |
10 |
Correct |
18 ms |
30804 KB |
Output is correct |
11 |
Correct |
17 ms |
30896 KB |
Output is correct |
12 |
Correct |
18 ms |
30864 KB |
Output is correct |
13 |
Correct |
18 ms |
30984 KB |
Output is correct |
14 |
Correct |
17 ms |
30916 KB |
Output is correct |
15 |
Correct |
17 ms |
30964 KB |
Output is correct |
16 |
Correct |
18 ms |
30932 KB |
Output is correct |
17 |
Correct |
17 ms |
30936 KB |
Output is correct |
18 |
Correct |
16 ms |
30932 KB |
Output is correct |
19 |
Correct |
48 ms |
32484 KB |
Output is correct |
20 |
Correct |
55 ms |
32648 KB |
Output is correct |
21 |
Correct |
72 ms |
32916 KB |
Output is correct |
22 |
Correct |
62 ms |
33356 KB |
Output is correct |
23 |
Correct |
147 ms |
39940 KB |
Output is correct |
24 |
Correct |
164 ms |
42764 KB |
Output is correct |
25 |
Correct |
189 ms |
44492 KB |
Output is correct |
26 |
Correct |
212 ms |
46496 KB |
Output is correct |
27 |
Correct |
18 ms |
30836 KB |
Output is correct |
28 |
Correct |
16 ms |
30864 KB |
Output is correct |
29 |
Correct |
20 ms |
30876 KB |
Output is correct |
30 |
Correct |
45 ms |
31064 KB |
Output is correct |
31 |
Correct |
95 ms |
31472 KB |
Output is correct |
32 |
Correct |
16 ms |
30804 KB |
Output is correct |
33 |
Correct |
18 ms |
31016 KB |
Output is correct |
34 |
Correct |
22 ms |
31060 KB |
Output is correct |
35 |
Correct |
19 ms |
31060 KB |
Output is correct |
36 |
Correct |
46 ms |
31264 KB |
Output is correct |
37 |
Correct |
138 ms |
31780 KB |
Output is correct |
38 |
Correct |
29 ms |
33152 KB |
Output is correct |
39 |
Correct |
26 ms |
33236 KB |
Output is correct |
40 |
Correct |
29 ms |
33248 KB |
Output is correct |
41 |
Correct |
69 ms |
33432 KB |
Output is correct |
42 |
Correct |
197 ms |
33756 KB |
Output is correct |
43 |
Correct |
288 ms |
78572 KB |
Output is correct |
44 |
Correct |
307 ms |
78492 KB |
Output is correct |
45 |
Correct |
288 ms |
78488 KB |
Output is correct |
46 |
Correct |
340 ms |
78820 KB |
Output is correct |
47 |
Correct |
648 ms |
79260 KB |
Output is correct |
48 |
Correct |
30 ms |
33100 KB |
Output is correct |
49 |
Correct |
69 ms |
33108 KB |
Output is correct |
50 |
Correct |
297 ms |
33484 KB |
Output is correct |
51 |
Correct |
417 ms |
33736 KB |
Output is correct |
52 |
Correct |
176 ms |
60756 KB |
Output is correct |
53 |
Correct |
289 ms |
60988 KB |
Output is correct |
54 |
Correct |
613 ms |
61244 KB |
Output is correct |
55 |
Correct |
1045 ms |
61428 KB |
Output is correct |
56 |
Correct |
1034 ms |
210496 KB |
Output is correct |
57 |
Correct |
1140 ms |
210440 KB |
Output is correct |
58 |
Correct |
1739 ms |
210748 KB |
Output is correct |
59 |
Correct |
2556 ms |
210920 KB |
Output is correct |
60 |
Correct |
2129 ms |
414632 KB |
Output is correct |
61 |
Correct |
2376 ms |
414560 KB |
Output is correct |
62 |
Correct |
3064 ms |
414816 KB |
Output is correct |
63 |
Correct |
3919 ms |
415144 KB |
Output is correct |
64 |
Execution timed out |
5060 ms |
415064 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |