#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 1e5 + 5;
const int LG = 17;
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 |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9700 KB |
Output is correct |
3 |
Correct |
5 ms |
9812 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
5 ms |
9740 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
7 ms |
9812 KB |
Output is correct |
8 |
Correct |
5 ms |
9776 KB |
Output is correct |
9 |
Correct |
6 ms |
9744 KB |
Output is correct |
10 |
Correct |
5 ms |
9812 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
6 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9812 KB |
Output is correct |
18 |
Correct |
6 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9700 KB |
Output is correct |
3 |
Correct |
5 ms |
9812 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
5 ms |
9740 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
7 ms |
9812 KB |
Output is correct |
8 |
Correct |
5 ms |
9776 KB |
Output is correct |
9 |
Correct |
6 ms |
9744 KB |
Output is correct |
10 |
Correct |
5 ms |
9812 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
6 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9812 KB |
Output is correct |
18 |
Correct |
6 ms |
9812 KB |
Output is correct |
19 |
Correct |
33 ms |
10452 KB |
Output is correct |
20 |
Correct |
36 ms |
10488 KB |
Output is correct |
21 |
Correct |
39 ms |
10552 KB |
Output is correct |
22 |
Correct |
57 ms |
10620 KB |
Output is correct |
23 |
Correct |
55 ms |
13012 KB |
Output is correct |
24 |
Correct |
66 ms |
13384 KB |
Output is correct |
25 |
Correct |
73 ms |
13608 KB |
Output is correct |
26 |
Correct |
79 ms |
14156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9780 KB |
Output is correct |
3 |
Correct |
14 ms |
9776 KB |
Output is correct |
4 |
Correct |
54 ms |
9852 KB |
Output is correct |
5 |
Correct |
225 ms |
10192 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
7 ms |
9940 KB |
Output is correct |
8 |
Correct |
6 ms |
9940 KB |
Output is correct |
9 |
Correct |
12 ms |
9940 KB |
Output is correct |
10 |
Correct |
58 ms |
10028 KB |
Output is correct |
11 |
Correct |
284 ms |
10436 KB |
Output is correct |
12 |
Correct |
11 ms |
11988 KB |
Output is correct |
13 |
Correct |
11 ms |
11988 KB |
Output is correct |
14 |
Correct |
16 ms |
12008 KB |
Output is correct |
15 |
Correct |
70 ms |
12036 KB |
Output is correct |
16 |
Correct |
293 ms |
12500 KB |
Output is correct |
17 |
Incorrect |
155 ms |
53304 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
10520 KB |
Output is correct |
2 |
Correct |
57 ms |
10636 KB |
Output is correct |
3 |
Correct |
251 ms |
10740 KB |
Output is correct |
4 |
Correct |
487 ms |
11176 KB |
Output is correct |
5 |
Correct |
45 ms |
17480 KB |
Output is correct |
6 |
Correct |
117 ms |
17528 KB |
Output is correct |
7 |
Correct |
439 ms |
17684 KB |
Output is correct |
8 |
Correct |
837 ms |
18044 KB |
Output is correct |
9 |
Correct |
252 ms |
51464 KB |
Output is correct |
10 |
Correct |
365 ms |
51488 KB |
Output is correct |
11 |
Correct |
835 ms |
51724 KB |
Output is correct |
12 |
Correct |
1484 ms |
52020 KB |
Output is correct |
13 |
Incorrect |
514 ms |
75528 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4386 ms |
114432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9700 KB |
Output is correct |
3 |
Correct |
5 ms |
9812 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
5 ms |
9740 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
7 ms |
9812 KB |
Output is correct |
8 |
Correct |
5 ms |
9776 KB |
Output is correct |
9 |
Correct |
6 ms |
9744 KB |
Output is correct |
10 |
Correct |
5 ms |
9812 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
6 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9812 KB |
Output is correct |
18 |
Correct |
6 ms |
9812 KB |
Output is correct |
19 |
Correct |
33 ms |
10452 KB |
Output is correct |
20 |
Correct |
36 ms |
10488 KB |
Output is correct |
21 |
Correct |
39 ms |
10552 KB |
Output is correct |
22 |
Correct |
57 ms |
10620 KB |
Output is correct |
23 |
Correct |
55 ms |
13012 KB |
Output is correct |
24 |
Correct |
66 ms |
13384 KB |
Output is correct |
25 |
Correct |
73 ms |
13608 KB |
Output is correct |
26 |
Correct |
79 ms |
14156 KB |
Output is correct |
27 |
Correct |
5 ms |
9684 KB |
Output is correct |
28 |
Correct |
7 ms |
9780 KB |
Output is correct |
29 |
Correct |
14 ms |
9776 KB |
Output is correct |
30 |
Correct |
54 ms |
9852 KB |
Output is correct |
31 |
Correct |
225 ms |
10192 KB |
Output is correct |
32 |
Correct |
5 ms |
9684 KB |
Output is correct |
33 |
Correct |
7 ms |
9940 KB |
Output is correct |
34 |
Correct |
6 ms |
9940 KB |
Output is correct |
35 |
Correct |
12 ms |
9940 KB |
Output is correct |
36 |
Correct |
58 ms |
10028 KB |
Output is correct |
37 |
Correct |
284 ms |
10436 KB |
Output is correct |
38 |
Correct |
11 ms |
11988 KB |
Output is correct |
39 |
Correct |
11 ms |
11988 KB |
Output is correct |
40 |
Correct |
16 ms |
12008 KB |
Output is correct |
41 |
Correct |
70 ms |
12036 KB |
Output is correct |
42 |
Correct |
293 ms |
12500 KB |
Output is correct |
43 |
Incorrect |
155 ms |
53304 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |