#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; scanf("%d %lld", &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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:156:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | int ee; ll wt; scanf("%d %lld", &ee, &wt);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19216 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
13 ms |
19236 KB |
Output is correct |
5 |
Correct |
13 ms |
19232 KB |
Output is correct |
6 |
Correct |
14 ms |
19156 KB |
Output is correct |
7 |
Correct |
11 ms |
19156 KB |
Output is correct |
8 |
Correct |
11 ms |
19212 KB |
Output is correct |
9 |
Correct |
12 ms |
19292 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19284 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
13 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
12 ms |
19304 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
12 ms |
19284 KB |
Output is correct |
18 |
Correct |
13 ms |
19332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19216 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
13 ms |
19236 KB |
Output is correct |
5 |
Correct |
13 ms |
19232 KB |
Output is correct |
6 |
Correct |
14 ms |
19156 KB |
Output is correct |
7 |
Correct |
11 ms |
19156 KB |
Output is correct |
8 |
Correct |
11 ms |
19212 KB |
Output is correct |
9 |
Correct |
12 ms |
19292 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19284 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
13 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
12 ms |
19304 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
12 ms |
19284 KB |
Output is correct |
18 |
Correct |
13 ms |
19332 KB |
Output is correct |
19 |
Correct |
29 ms |
19932 KB |
Output is correct |
20 |
Correct |
34 ms |
19912 KB |
Output is correct |
21 |
Correct |
37 ms |
19976 KB |
Output is correct |
22 |
Correct |
43 ms |
20068 KB |
Output is correct |
23 |
Correct |
47 ms |
22484 KB |
Output is correct |
24 |
Correct |
59 ms |
22820 KB |
Output is correct |
25 |
Correct |
74 ms |
23124 KB |
Output is correct |
26 |
Correct |
79 ms |
23660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19104 KB |
Output is correct |
2 |
Correct |
12 ms |
19088 KB |
Output is correct |
3 |
Correct |
12 ms |
19156 KB |
Output is correct |
4 |
Correct |
25 ms |
19284 KB |
Output is correct |
5 |
Correct |
79 ms |
19688 KB |
Output is correct |
6 |
Correct |
10 ms |
19156 KB |
Output is correct |
7 |
Correct |
11 ms |
19412 KB |
Output is correct |
8 |
Correct |
11 ms |
19412 KB |
Output is correct |
9 |
Correct |
13 ms |
19432 KB |
Output is correct |
10 |
Correct |
31 ms |
19508 KB |
Output is correct |
11 |
Correct |
116 ms |
19872 KB |
Output is correct |
12 |
Correct |
15 ms |
21460 KB |
Output is correct |
13 |
Correct |
16 ms |
21460 KB |
Output is correct |
14 |
Correct |
19 ms |
21460 KB |
Output is correct |
15 |
Correct |
41 ms |
21580 KB |
Output is correct |
16 |
Correct |
166 ms |
21944 KB |
Output is correct |
17 |
Correct |
138 ms |
64976 KB |
Output is correct |
18 |
Correct |
166 ms |
65056 KB |
Output is correct |
19 |
Correct |
156 ms |
65180 KB |
Output is correct |
20 |
Correct |
231 ms |
65080 KB |
Output is correct |
21 |
Correct |
423 ms |
65576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19924 KB |
Output is correct |
2 |
Correct |
46 ms |
19980 KB |
Output is correct |
3 |
Correct |
179 ms |
20120 KB |
Output is correct |
4 |
Correct |
346 ms |
20392 KB |
Output is correct |
5 |
Correct |
48 ms |
27080 KB |
Output is correct |
6 |
Correct |
101 ms |
27128 KB |
Output is correct |
7 |
Correct |
378 ms |
27364 KB |
Output is correct |
8 |
Correct |
637 ms |
27676 KB |
Output is correct |
9 |
Correct |
241 ms |
61780 KB |
Output is correct |
10 |
Correct |
366 ms |
61636 KB |
Output is correct |
11 |
Correct |
780 ms |
62024 KB |
Output is correct |
12 |
Correct |
1259 ms |
62260 KB |
Output is correct |
13 |
Correct |
545 ms |
107084 KB |
Output is correct |
14 |
Correct |
646 ms |
107144 KB |
Output is correct |
15 |
Correct |
1128 ms |
107316 KB |
Output is correct |
16 |
Correct |
1745 ms |
107836 KB |
Output is correct |
17 |
Correct |
2900 ms |
107832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2947 ms |
98100 KB |
Output is correct |
2 |
Correct |
3291 ms |
99376 KB |
Output is correct |
3 |
Correct |
3106 ms |
98968 KB |
Output is correct |
4 |
Correct |
3037 ms |
99368 KB |
Output is correct |
5 |
Correct |
2673 ms |
96728 KB |
Output is correct |
6 |
Correct |
2325 ms |
85224 KB |
Output is correct |
7 |
Correct |
4034 ms |
112216 KB |
Output is correct |
8 |
Correct |
4275 ms |
112116 KB |
Output is correct |
9 |
Correct |
4035 ms |
112184 KB |
Output is correct |
10 |
Correct |
4272 ms |
111968 KB |
Output is correct |
11 |
Correct |
3888 ms |
108892 KB |
Output is correct |
12 |
Correct |
3415 ms |
92388 KB |
Output is correct |
13 |
Execution timed out |
5039 ms |
120108 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
11 ms |
19216 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
13 ms |
19236 KB |
Output is correct |
5 |
Correct |
13 ms |
19232 KB |
Output is correct |
6 |
Correct |
14 ms |
19156 KB |
Output is correct |
7 |
Correct |
11 ms |
19156 KB |
Output is correct |
8 |
Correct |
11 ms |
19212 KB |
Output is correct |
9 |
Correct |
12 ms |
19292 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19284 KB |
Output is correct |
12 |
Correct |
11 ms |
19284 KB |
Output is correct |
13 |
Correct |
13 ms |
19284 KB |
Output is correct |
14 |
Correct |
11 ms |
19284 KB |
Output is correct |
15 |
Correct |
12 ms |
19304 KB |
Output is correct |
16 |
Correct |
11 ms |
19284 KB |
Output is correct |
17 |
Correct |
12 ms |
19284 KB |
Output is correct |
18 |
Correct |
13 ms |
19332 KB |
Output is correct |
19 |
Correct |
29 ms |
19932 KB |
Output is correct |
20 |
Correct |
34 ms |
19912 KB |
Output is correct |
21 |
Correct |
37 ms |
19976 KB |
Output is correct |
22 |
Correct |
43 ms |
20068 KB |
Output is correct |
23 |
Correct |
47 ms |
22484 KB |
Output is correct |
24 |
Correct |
59 ms |
22820 KB |
Output is correct |
25 |
Correct |
74 ms |
23124 KB |
Output is correct |
26 |
Correct |
79 ms |
23660 KB |
Output is correct |
27 |
Correct |
11 ms |
19104 KB |
Output is correct |
28 |
Correct |
12 ms |
19088 KB |
Output is correct |
29 |
Correct |
12 ms |
19156 KB |
Output is correct |
30 |
Correct |
25 ms |
19284 KB |
Output is correct |
31 |
Correct |
79 ms |
19688 KB |
Output is correct |
32 |
Correct |
10 ms |
19156 KB |
Output is correct |
33 |
Correct |
11 ms |
19412 KB |
Output is correct |
34 |
Correct |
11 ms |
19412 KB |
Output is correct |
35 |
Correct |
13 ms |
19432 KB |
Output is correct |
36 |
Correct |
31 ms |
19508 KB |
Output is correct |
37 |
Correct |
116 ms |
19872 KB |
Output is correct |
38 |
Correct |
15 ms |
21460 KB |
Output is correct |
39 |
Correct |
16 ms |
21460 KB |
Output is correct |
40 |
Correct |
19 ms |
21460 KB |
Output is correct |
41 |
Correct |
41 ms |
21580 KB |
Output is correct |
42 |
Correct |
166 ms |
21944 KB |
Output is correct |
43 |
Correct |
138 ms |
64976 KB |
Output is correct |
44 |
Correct |
166 ms |
65056 KB |
Output is correct |
45 |
Correct |
156 ms |
65180 KB |
Output is correct |
46 |
Correct |
231 ms |
65080 KB |
Output is correct |
47 |
Correct |
423 ms |
65576 KB |
Output is correct |
48 |
Correct |
16 ms |
19924 KB |
Output is correct |
49 |
Correct |
46 ms |
19980 KB |
Output is correct |
50 |
Correct |
179 ms |
20120 KB |
Output is correct |
51 |
Correct |
346 ms |
20392 KB |
Output is correct |
52 |
Correct |
48 ms |
27080 KB |
Output is correct |
53 |
Correct |
101 ms |
27128 KB |
Output is correct |
54 |
Correct |
378 ms |
27364 KB |
Output is correct |
55 |
Correct |
637 ms |
27676 KB |
Output is correct |
56 |
Correct |
241 ms |
61780 KB |
Output is correct |
57 |
Correct |
366 ms |
61636 KB |
Output is correct |
58 |
Correct |
780 ms |
62024 KB |
Output is correct |
59 |
Correct |
1259 ms |
62260 KB |
Output is correct |
60 |
Correct |
545 ms |
107084 KB |
Output is correct |
61 |
Correct |
646 ms |
107144 KB |
Output is correct |
62 |
Correct |
1128 ms |
107316 KB |
Output is correct |
63 |
Correct |
1745 ms |
107836 KB |
Output is correct |
64 |
Correct |
2900 ms |
107832 KB |
Output is correct |
65 |
Correct |
2947 ms |
98100 KB |
Output is correct |
66 |
Correct |
3291 ms |
99376 KB |
Output is correct |
67 |
Correct |
3106 ms |
98968 KB |
Output is correct |
68 |
Correct |
3037 ms |
99368 KB |
Output is correct |
69 |
Correct |
2673 ms |
96728 KB |
Output is correct |
70 |
Correct |
2325 ms |
85224 KB |
Output is correct |
71 |
Correct |
4034 ms |
112216 KB |
Output is correct |
72 |
Correct |
4275 ms |
112116 KB |
Output is correct |
73 |
Correct |
4035 ms |
112184 KB |
Output is correct |
74 |
Correct |
4272 ms |
111968 KB |
Output is correct |
75 |
Correct |
3888 ms |
108892 KB |
Output is correct |
76 |
Correct |
3415 ms |
92388 KB |
Output is correct |
77 |
Execution timed out |
5039 ms |
120108 KB |
Time limit exceeded |
78 |
Halted |
0 ms |
0 KB |
- |