#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];
vector<int> partOf[maxn];
vector<ll> seg[maxn],lazy[maxn];
bool isCent[maxn];
int subSz[maxn],timer[maxn];
unordered_map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn];
unordered_map<int,ll> costEdge[maxn];
ll tempResult[maxn];
priority_queue<pair<ll,int> > 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;
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));
}
}
int32_t 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);
cost[i] = w;
}
auto now = clock();
dfsCent(0,-1);
for(int i=1;i<n;i++){
for(int it : partOf[i]){
int z = edgeRoot[it][i];
upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,cost[i]);
costEdge[it][z] = qry(it,1,0,timer[it]-1,tin[it][z],tout[it][z]);
bestEdge[it].emplace(costEdge[it][z],z);
}
}
for(int i=0;i<n;i++){
vector<pair<ll,int> > best;
while(!bestEdge[i].empty() && best.size() < 2){
auto [u,v] = bestEdge[i].top();
bestEdge[i].pop();
if(costEdge[i][v] == u && (best.empty() || best.back() != make_pair(u,v))){
best.emplace_back(u,v);
}
}
ll sum = 0;
for(auto it : best){
sum += it.first;
}
for(auto it : best){
bestEdge[i].emplace(it);
}
tempResult[i] = sum;
result.emplace(tempResult[i],i);
}
assert(clock()-now <= 6000);
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]){
int z = edgeRoot[it][i];
upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,df);
costEdge[it][z] = qry(it,1,0,timer[it]-1,tin[it][z],tout[it][z]);
bestEdge[it].emplace(costEdge[it][z],z);
vector<pair<ll,int> > best;
while(!bestEdge[it].empty() && best.size() < 2){
auto [u,v] = bestEdge[it].top();
bestEdge[it].pop();
if(costEdge[it][v] == u && (best.empty() || best.back() != make_pair(u,v))){
best.emplace_back(u,v);
}
}
ll sum = 0;
for(auto it2 : best){
sum += it2.first;
}
for(auto it2 : best){
bestEdge[it].emplace(it2);
}
tempResult[it] = sum;
result.emplace(tempResult[it],it);
}
cost[i] = j;
while(true){
auto [u,v] = result.top();
if(tempResult[v] == u){
break;
}
result.pop();
}
last = result.top().first;
cout << result.top().first << "\n";
}
}
Compilation message
diameter.cpp: In function 'void dfsSz(int, int)':
diameter.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
21 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'int fnCent(int, int, int)':
diameter.cpp:29:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsTour(int, int, int)':
diameter.cpp:37:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsEdgeRoot(int, int, int, int)':
diameter.cpp:47:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | for(auto [v,w] : adj[u]){
| ^
diameter.cpp: In function 'void dfsCent(int, int)':
diameter.cpp:59:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | for(auto [v,w] : adj[cent]){
| ^
diameter.cpp:68:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for(auto [v,w] : adj[cent]){
| ^
diameter.cpp: In function 'int32_t main()':
diameter.cpp:138:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
138 | auto [u,v] = bestEdge[i].top();
| ^
diameter.cpp:170:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
170 | auto [u,v] = bestEdge[it].top();
| ^
diameter.cpp:188:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
188 | auto [u,v] = result.top();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
34772 KB |
Output is correct |
2 |
Correct |
19 ms |
34772 KB |
Output is correct |
3 |
Correct |
24 ms |
34800 KB |
Output is correct |
4 |
Correct |
19 ms |
34692 KB |
Output is correct |
5 |
Correct |
19 ms |
34792 KB |
Output is correct |
6 |
Correct |
19 ms |
34792 KB |
Output is correct |
7 |
Correct |
19 ms |
34844 KB |
Output is correct |
8 |
Correct |
20 ms |
34804 KB |
Output is correct |
9 |
Correct |
19 ms |
34772 KB |
Output is correct |
10 |
Correct |
19 ms |
34844 KB |
Output is correct |
11 |
Correct |
19 ms |
34776 KB |
Output is correct |
12 |
Correct |
19 ms |
34804 KB |
Output is correct |
13 |
Correct |
20 ms |
34868 KB |
Output is correct |
14 |
Correct |
20 ms |
34780 KB |
Output is correct |
15 |
Correct |
20 ms |
34868 KB |
Output is correct |
16 |
Correct |
19 ms |
34900 KB |
Output is correct |
17 |
Correct |
20 ms |
34892 KB |
Output is correct |
18 |
Correct |
20 ms |
34900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
34772 KB |
Output is correct |
2 |
Correct |
19 ms |
34772 KB |
Output is correct |
3 |
Correct |
24 ms |
34800 KB |
Output is correct |
4 |
Correct |
19 ms |
34692 KB |
Output is correct |
5 |
Correct |
19 ms |
34792 KB |
Output is correct |
6 |
Correct |
19 ms |
34792 KB |
Output is correct |
7 |
Correct |
19 ms |
34844 KB |
Output is correct |
8 |
Correct |
20 ms |
34804 KB |
Output is correct |
9 |
Correct |
19 ms |
34772 KB |
Output is correct |
10 |
Correct |
19 ms |
34844 KB |
Output is correct |
11 |
Correct |
19 ms |
34776 KB |
Output is correct |
12 |
Correct |
19 ms |
34804 KB |
Output is correct |
13 |
Correct |
20 ms |
34868 KB |
Output is correct |
14 |
Correct |
20 ms |
34780 KB |
Output is correct |
15 |
Correct |
20 ms |
34868 KB |
Output is correct |
16 |
Correct |
19 ms |
34900 KB |
Output is correct |
17 |
Correct |
20 ms |
34892 KB |
Output is correct |
18 |
Correct |
20 ms |
34900 KB |
Output is correct |
19 |
Correct |
47 ms |
36796 KB |
Output is correct |
20 |
Correct |
48 ms |
36980 KB |
Output is correct |
21 |
Correct |
57 ms |
37232 KB |
Output is correct |
22 |
Runtime error |
56 ms |
75448 KB |
Execution killed with signal 6 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
34792 KB |
Output is correct |
2 |
Correct |
19 ms |
34776 KB |
Output is correct |
3 |
Correct |
20 ms |
34772 KB |
Output is correct |
4 |
Correct |
37 ms |
34900 KB |
Output is correct |
5 |
Correct |
110 ms |
35528 KB |
Output is correct |
6 |
Correct |
20 ms |
34724 KB |
Output is correct |
7 |
Correct |
20 ms |
34936 KB |
Output is correct |
8 |
Correct |
20 ms |
35028 KB |
Output is correct |
9 |
Correct |
30 ms |
34984 KB |
Output is correct |
10 |
Correct |
41 ms |
35416 KB |
Output is correct |
11 |
Correct |
119 ms |
36392 KB |
Output is correct |
12 |
Correct |
26 ms |
36960 KB |
Output is correct |
13 |
Correct |
26 ms |
37060 KB |
Output is correct |
14 |
Correct |
28 ms |
37072 KB |
Output is correct |
15 |
Correct |
48 ms |
37460 KB |
Output is correct |
16 |
Correct |
141 ms |
38252 KB |
Output is correct |
17 |
Runtime error |
204 ms |
164340 KB |
Execution killed with signal 6 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
37032 KB |
Output is correct |
2 |
Correct |
61 ms |
37704 KB |
Output is correct |
3 |
Correct |
197 ms |
39512 KB |
Output is correct |
4 |
Correct |
398 ms |
41832 KB |
Output is correct |
5 |
Runtime error |
173 ms |
134936 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2576 ms |
691476 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
34772 KB |
Output is correct |
2 |
Correct |
19 ms |
34772 KB |
Output is correct |
3 |
Correct |
24 ms |
34800 KB |
Output is correct |
4 |
Correct |
19 ms |
34692 KB |
Output is correct |
5 |
Correct |
19 ms |
34792 KB |
Output is correct |
6 |
Correct |
19 ms |
34792 KB |
Output is correct |
7 |
Correct |
19 ms |
34844 KB |
Output is correct |
8 |
Correct |
20 ms |
34804 KB |
Output is correct |
9 |
Correct |
19 ms |
34772 KB |
Output is correct |
10 |
Correct |
19 ms |
34844 KB |
Output is correct |
11 |
Correct |
19 ms |
34776 KB |
Output is correct |
12 |
Correct |
19 ms |
34804 KB |
Output is correct |
13 |
Correct |
20 ms |
34868 KB |
Output is correct |
14 |
Correct |
20 ms |
34780 KB |
Output is correct |
15 |
Correct |
20 ms |
34868 KB |
Output is correct |
16 |
Correct |
19 ms |
34900 KB |
Output is correct |
17 |
Correct |
20 ms |
34892 KB |
Output is correct |
18 |
Correct |
20 ms |
34900 KB |
Output is correct |
19 |
Correct |
47 ms |
36796 KB |
Output is correct |
20 |
Correct |
48 ms |
36980 KB |
Output is correct |
21 |
Correct |
57 ms |
37232 KB |
Output is correct |
22 |
Runtime error |
56 ms |
75448 KB |
Execution killed with signal 6 |
23 |
Halted |
0 ms |
0 KB |
- |