#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 2e5 + 5;
const int LG = 18;
const ll inf = 4e18 + 69;
#define ll long long
int n, q; ll wtwtwt;
vector<pair<pair<int, int>, ll> > edges;
vector<int> adj[MX];
struct SegmentTree{
ll st[MX], lz[MX];
#define cm (cl + cr) / 2
#define lc nd + 1
#define rc nd + 2 * (cm - cl + 1)
void prop(int nd, int cl, int cr){
if(lz[nd]){
st[nd] += lz[nd];
if(cl != cr){
lz[lc] += lz[nd];
lz[rc] += lz[nd];
}
lz[nd] = 0;
}
}
void upd(int nd, int cl, int cr, int lf, int rg, ll vl){
prop(nd, cl, cr);
if(cr < lf || rg < cl) return;
if(lf <= cl && cr <= rg){
lz[nd] += vl;
prop(nd, cl, cr);
return;
}
upd(lc, cl, cm, lf, rg, vl);
upd(rc, cm + 1, cr, lf, rg, vl);
st[nd] = max(st[lc], st[rc]);
}
ll que(int nd, int cl, int cr, int lf, int rg){
prop(nd, cl, cr);
if(cr < lf || rg < cl) return -1;
if(lf <= cl && cr <= rg) return st[nd];
ll L = que(lc, cl, cm, lf, rg);
ll R = que(rc, cm + 1, cr, lf, rg);
return max(L, R);
}
} st[LG];
struct SegmentTreeIterative{
ll st[MX << 1];
void upd(int ps, ll vl){
for(ps += MX, st[ps] = vl, ps >>= 1; ps > 0; ps >>= 1) st[ps] = max(st[ps << 1], st[ps << 1 | 1]);
}
ll que(ll lf, ll rg){
ll rs = 0ll;
for(lf += MX, rg += MX + 1; lf < rg; lf >>= 1, rg >>= 1){
if(lf & 1) rs = max(st[lf ++], rs);
if(rg & 1) rs = max(rs, st[-- rg]);
}
return rs;
}
} stdp;
bool vis[MX], dead[MX];
int sz[MX];
void dfssz(int nw, int bf){
sz[nw] = 1;
for(int nx : adj[nw]) if(nx != bf && !dead[nx]){
dfssz(nx, nw);
sz[nw] += sz[nx];
}
}
int cent = -1, ccsz = 0;
void dfscent(int nw, int bf){
for(int nx : adj[nw]) if(nx != bf && !dead[nx]) dfscent(nx, nw);
if(cent == -1 && sz[nw] >= (ccsz + 1) / 2) cent = nw;
}
int layer = 0, tin[MX][LG], tim[LG], tout[MX][LG], rt[MX][LG], par[MX][LG], layer_id[MX];
void init(int nw, int bf){
rt[nw][layer] = cent;
tin[nw][layer] = ++ tim[layer];
par[nw][layer] = bf;
for(int nx : adj[nw]) if(nx != bf && !dead[nx]) init(nx, nw);
tout[nw][layer] = tim[layer];
}
vector<pair<int, int> > adj_root[MX];
void findCentroid(int nw){
dfssz(nw, 0);
cent = -1, ccsz = sz[nw];
dfscent(nw, 0);
init(cent, 0); layer_id[cent] = layer;
for(int nx : adj[cent]) if(!dead[nx])
adj_root[cent].push_back({tin[nx][layer], nx});
sort(adj_root[cent].begin(), adj_root[cent].end());
dead[cent] = 1;
for(int nx : adj[cent]) if(!dead[nx]){
layer ++;
findCentroid(nx);
layer --;
}
}
set<pair<ll, int> > dp[MX];
int main(){
scanf("%d %d %lld", &n, &q, &wtwtwt);
for(int i = 1; i < n; i ++){
int u, v; ll w;
scanf("%d %d %lld", &u, &v, &w);
adj[u].push_back(v);
adj[v].push_back(u);
edges.push_back({{u, v}, w});
}
findCentroid(1);
for(auto e : edges){
int u = e.first.first, v = e.first.second; ll w = e.second;
for(int j = 0; j < LG; j ++){
if(rt[u][j] != rt[v][j]) break;
if(tin[u][j] < tin[v][j]) swap(u, v);
st[j].upd(1, 1, n, tin[u][j], tout[u][j], w);
}
}
for(int i = 1; i <= n; i ++){
for(pair<int, int> nx : adj_root[i])
dp[i].insert({st[layer_id[i]].que(1, 1, n, tin[nx.second][layer_id[i]], tout[nx.second][layer_id[i]]), tin[nx.second][layer_id[i]]});
ll res = 0ll;
auto it = dp[i].end();
for(int _ = 0; _ < 2; _ ++) if(it != dp[i].begin()){
it = prev(it);
res += (*it).first;
}
stdp.upd(i, res);
}
ll last_answer = 0ll;
for(; q --;){
int ee; ll wt; cin >> ee >> wt;
ee = (int)((ee + last_answer) % (n - 1));
wt = (wt + last_answer) % wtwtwt;
int u = edges[ee].first.first, v = edges[ee].first.second; ll wtchange = wt - edges[ee].second;
for(int j = 0; j < LG; j ++){
if(rt[u][j] != rt[v][j]) break;
if(tin[u][j] < tin[v][j]) swap(u, v);
int uid = lower_bound(adj_root[rt[u][j]].begin(), adj_root[rt[u][j]].end(), make_pair(tin[u][j] + 1, -1)) - adj_root[rt[u][j]].begin();
int anc = adj_root[rt[u][j]][uid - 1].second;
dp[rt[u][j]].erase(make_pair(st[j].que(1, 1, n, tin[anc][j], tout[anc][j]), tin[anc][j]));
st[j].upd(1, 1, n, tin[u][j], tout[u][j], wtchange);
dp[rt[u][j]].insert(make_pair(st[j].que(1, 1, n, tin[anc][j], tout[anc][j]), tin[anc][j]));
ll res = 0ll;
auto it = dp[rt[u][j]].end();
for(int _ = 0; _ < 2; _ ++) if(it != dp[rt[u][j]].begin()){
it = prev(it);
res += (*it).first;
}
stdp.upd(rt[u][j], res);
}
edges[ee].second = wt;
last_answer = stdp.que(1, n);
printf("%lld\n", last_answer);
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%d %d %lld", &n, &q, &wtwtwt);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d %d %lld", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19156 KB |
Output is correct |
3 |
Correct |
11 ms |
19156 KB |
Output is correct |
4 |
Correct |
12 ms |
19152 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19144 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
13 ms |
19184 KB |
Output is correct |
9 |
Correct |
12 ms |
19284 KB |
Output is correct |
10 |
Correct |
12 ms |
19220 KB |
Output is correct |
11 |
Correct |
11 ms |
19180 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
11 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
11 ms |
19284 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
11 ms |
19212 KB |
Output is correct |
18 |
Correct |
10 ms |
19284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19156 KB |
Output is correct |
3 |
Correct |
11 ms |
19156 KB |
Output is correct |
4 |
Correct |
12 ms |
19152 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19144 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
13 ms |
19184 KB |
Output is correct |
9 |
Correct |
12 ms |
19284 KB |
Output is correct |
10 |
Correct |
12 ms |
19220 KB |
Output is correct |
11 |
Correct |
11 ms |
19180 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
11 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
11 ms |
19284 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
11 ms |
19212 KB |
Output is correct |
18 |
Correct |
10 ms |
19284 KB |
Output is correct |
19 |
Correct |
50 ms |
19924 KB |
Output is correct |
20 |
Correct |
50 ms |
19908 KB |
Output is correct |
21 |
Correct |
45 ms |
19996 KB |
Output is correct |
22 |
Correct |
49 ms |
20168 KB |
Output is correct |
23 |
Correct |
66 ms |
22556 KB |
Output is correct |
24 |
Correct |
76 ms |
22908 KB |
Output is correct |
25 |
Correct |
83 ms |
23072 KB |
Output is correct |
26 |
Correct |
89 ms |
23680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19156 KB |
Output is correct |
3 |
Correct |
15 ms |
19212 KB |
Output is correct |
4 |
Correct |
53 ms |
19236 KB |
Output is correct |
5 |
Correct |
258 ms |
19564 KB |
Output is correct |
6 |
Correct |
11 ms |
19156 KB |
Output is correct |
7 |
Correct |
12 ms |
19412 KB |
Output is correct |
8 |
Correct |
12 ms |
19412 KB |
Output is correct |
9 |
Correct |
16 ms |
19436 KB |
Output is correct |
10 |
Correct |
61 ms |
19412 KB |
Output is correct |
11 |
Correct |
264 ms |
19964 KB |
Output is correct |
12 |
Correct |
15 ms |
21460 KB |
Output is correct |
13 |
Correct |
19 ms |
21460 KB |
Output is correct |
14 |
Correct |
21 ms |
21460 KB |
Output is correct |
15 |
Correct |
88 ms |
21552 KB |
Output is correct |
16 |
Correct |
299 ms |
22068 KB |
Output is correct |
17 |
Correct |
143 ms |
65072 KB |
Output is correct |
18 |
Correct |
152 ms |
65008 KB |
Output is correct |
19 |
Correct |
155 ms |
65204 KB |
Output is correct |
20 |
Correct |
228 ms |
65112 KB |
Output is correct |
21 |
Correct |
677 ms |
65664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
19924 KB |
Output is correct |
2 |
Correct |
60 ms |
19924 KB |
Output is correct |
3 |
Correct |
257 ms |
20172 KB |
Output is correct |
4 |
Correct |
493 ms |
20424 KB |
Output is correct |
5 |
Correct |
66 ms |
27080 KB |
Output is correct |
6 |
Correct |
120 ms |
27136 KB |
Output is correct |
7 |
Correct |
430 ms |
27308 KB |
Output is correct |
8 |
Correct |
871 ms |
27584 KB |
Output is correct |
9 |
Correct |
253 ms |
61612 KB |
Output is correct |
10 |
Correct |
364 ms |
61780 KB |
Output is correct |
11 |
Correct |
795 ms |
62140 KB |
Output is correct |
12 |
Correct |
1498 ms |
62284 KB |
Output is correct |
13 |
Correct |
516 ms |
107012 KB |
Output is correct |
14 |
Correct |
653 ms |
107156 KB |
Output is correct |
15 |
Correct |
1239 ms |
107532 KB |
Output is correct |
16 |
Correct |
1992 ms |
107760 KB |
Output is correct |
17 |
Correct |
3051 ms |
107860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2977 ms |
98080 KB |
Output is correct |
2 |
Correct |
3117 ms |
102752 KB |
Output is correct |
3 |
Correct |
2971 ms |
102420 KB |
Output is correct |
4 |
Correct |
3220 ms |
102936 KB |
Output is correct |
5 |
Correct |
3048 ms |
100256 KB |
Output is correct |
6 |
Correct |
2597 ms |
88712 KB |
Output is correct |
7 |
Correct |
4378 ms |
115656 KB |
Output is correct |
8 |
Correct |
4675 ms |
115780 KB |
Output is correct |
9 |
Correct |
4348 ms |
115740 KB |
Output is correct |
10 |
Correct |
4444 ms |
115580 KB |
Output is correct |
11 |
Correct |
4276 ms |
112472 KB |
Output is correct |
12 |
Correct |
3590 ms |
95972 KB |
Output is correct |
13 |
Correct |
4759 ms |
123892 KB |
Output is correct |
14 |
Correct |
4878 ms |
123824 KB |
Output is correct |
15 |
Correct |
4694 ms |
123860 KB |
Output is correct |
16 |
Correct |
4757 ms |
123504 KB |
Output is correct |
17 |
Correct |
4841 ms |
119364 KB |
Output is correct |
18 |
Correct |
3986 ms |
98676 KB |
Output is correct |
19 |
Correct |
4976 ms |
123960 KB |
Output is correct |
20 |
Execution timed out |
5087 ms |
123672 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19156 KB |
Output is correct |
3 |
Correct |
11 ms |
19156 KB |
Output is correct |
4 |
Correct |
12 ms |
19152 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19144 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
13 ms |
19184 KB |
Output is correct |
9 |
Correct |
12 ms |
19284 KB |
Output is correct |
10 |
Correct |
12 ms |
19220 KB |
Output is correct |
11 |
Correct |
11 ms |
19180 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
11 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
11 ms |
19284 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
11 ms |
19212 KB |
Output is correct |
18 |
Correct |
10 ms |
19284 KB |
Output is correct |
19 |
Correct |
50 ms |
19924 KB |
Output is correct |
20 |
Correct |
50 ms |
19908 KB |
Output is correct |
21 |
Correct |
45 ms |
19996 KB |
Output is correct |
22 |
Correct |
49 ms |
20168 KB |
Output is correct |
23 |
Correct |
66 ms |
22556 KB |
Output is correct |
24 |
Correct |
76 ms |
22908 KB |
Output is correct |
25 |
Correct |
83 ms |
23072 KB |
Output is correct |
26 |
Correct |
89 ms |
23680 KB |
Output is correct |
27 |
Correct |
10 ms |
19156 KB |
Output is correct |
28 |
Correct |
11 ms |
19156 KB |
Output is correct |
29 |
Correct |
15 ms |
19212 KB |
Output is correct |
30 |
Correct |
53 ms |
19236 KB |
Output is correct |
31 |
Correct |
258 ms |
19564 KB |
Output is correct |
32 |
Correct |
11 ms |
19156 KB |
Output is correct |
33 |
Correct |
12 ms |
19412 KB |
Output is correct |
34 |
Correct |
12 ms |
19412 KB |
Output is correct |
35 |
Correct |
16 ms |
19436 KB |
Output is correct |
36 |
Correct |
61 ms |
19412 KB |
Output is correct |
37 |
Correct |
264 ms |
19964 KB |
Output is correct |
38 |
Correct |
15 ms |
21460 KB |
Output is correct |
39 |
Correct |
19 ms |
21460 KB |
Output is correct |
40 |
Correct |
21 ms |
21460 KB |
Output is correct |
41 |
Correct |
88 ms |
21552 KB |
Output is correct |
42 |
Correct |
299 ms |
22068 KB |
Output is correct |
43 |
Correct |
143 ms |
65072 KB |
Output is correct |
44 |
Correct |
152 ms |
65008 KB |
Output is correct |
45 |
Correct |
155 ms |
65204 KB |
Output is correct |
46 |
Correct |
228 ms |
65112 KB |
Output is correct |
47 |
Correct |
677 ms |
65664 KB |
Output is correct |
48 |
Correct |
18 ms |
19924 KB |
Output is correct |
49 |
Correct |
60 ms |
19924 KB |
Output is correct |
50 |
Correct |
257 ms |
20172 KB |
Output is correct |
51 |
Correct |
493 ms |
20424 KB |
Output is correct |
52 |
Correct |
66 ms |
27080 KB |
Output is correct |
53 |
Correct |
120 ms |
27136 KB |
Output is correct |
54 |
Correct |
430 ms |
27308 KB |
Output is correct |
55 |
Correct |
871 ms |
27584 KB |
Output is correct |
56 |
Correct |
253 ms |
61612 KB |
Output is correct |
57 |
Correct |
364 ms |
61780 KB |
Output is correct |
58 |
Correct |
795 ms |
62140 KB |
Output is correct |
59 |
Correct |
1498 ms |
62284 KB |
Output is correct |
60 |
Correct |
516 ms |
107012 KB |
Output is correct |
61 |
Correct |
653 ms |
107156 KB |
Output is correct |
62 |
Correct |
1239 ms |
107532 KB |
Output is correct |
63 |
Correct |
1992 ms |
107760 KB |
Output is correct |
64 |
Correct |
3051 ms |
107860 KB |
Output is correct |
65 |
Correct |
2977 ms |
98080 KB |
Output is correct |
66 |
Correct |
3117 ms |
102752 KB |
Output is correct |
67 |
Correct |
2971 ms |
102420 KB |
Output is correct |
68 |
Correct |
3220 ms |
102936 KB |
Output is correct |
69 |
Correct |
3048 ms |
100256 KB |
Output is correct |
70 |
Correct |
2597 ms |
88712 KB |
Output is correct |
71 |
Correct |
4378 ms |
115656 KB |
Output is correct |
72 |
Correct |
4675 ms |
115780 KB |
Output is correct |
73 |
Correct |
4348 ms |
115740 KB |
Output is correct |
74 |
Correct |
4444 ms |
115580 KB |
Output is correct |
75 |
Correct |
4276 ms |
112472 KB |
Output is correct |
76 |
Correct |
3590 ms |
95972 KB |
Output is correct |
77 |
Correct |
4759 ms |
123892 KB |
Output is correct |
78 |
Correct |
4878 ms |
123824 KB |
Output is correct |
79 |
Correct |
4694 ms |
123860 KB |
Output is correct |
80 |
Correct |
4757 ms |
123504 KB |
Output is correct |
81 |
Correct |
4841 ms |
119364 KB |
Output is correct |
82 |
Correct |
3986 ms |
98676 KB |
Output is correct |
83 |
Correct |
4976 ms |
123960 KB |
Output is correct |
84 |
Execution timed out |
5087 ms |
123672 KB |
Time limit exceeded |
85 |
Halted |
0 ms |
0 KB |
- |