#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
struct IT{
int n;
vector<ll> t;
vector<ll> lz;
IT(){}
IT(int _n) {
n = _n;
t.resize(n * 4 + 7, 0);
lz.resize(n * 4 + 7, 0);
}
void push_down(int v)
{
for(int i = v * 2; i <= v * 2 + 1; i++) {
t[i] += lz[v];
lz[i] += lz[v];
}
lz[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, ll val)
{
if(l > r) return;
if(tl == l && tr == r) {
t[v] += val;
lz[v] += val;
}
else {
push_down(v);
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, min(r, tm), val);
update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
ll getmax(int v, int tl, int tr, int l, int r)
{
if(l > r) return 0;
if(tl == l && tr == r) return t[v];
push_down(v);
int tm = (tl + tr) / 2;
ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return max(m1, m2);
}
void update(int l, int r, ll val)
{
update(1, 1, n, l, r, val);
}
ll getmax(int l, int r)
{
return getmax(1, 1, n, l, r);
}
} seg[mxN];
struct ITmax{
int n;
vector<ll> t;
ITmax(){}
ITmax(int _n) {
n = _n;
t.resize(n * 4 + 7, 0);
}
void update(int v, int tl, int tr, int pos, ll val)
{
if(tl == tr) t[v] = val;
else {
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl, tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
ll getmax(int v, int tl, int tr, int l, int r)
{
if(l > r) return 0;
if(tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return max(m1, m2);
}
void update(int pos, ll val)
{
update(1, 1, n, pos, val);
}
ll getmax(int l, int r)
{
return getmax(1, 1, n, l, r);
}
} maxval;
struct item{
int _ll;
int rr;
int cc;
};
struct EDGES{
int u, v;
ll c;
} eddd[mxN];
int n;
int q;
ll lim;
ll sumnode = 0;
int depth[mxN];
int sub[mxN];
int par[mxN];
bool removed[mxN];
vector<pair<int, ll>> adj[mxN];
vector<int> lef[mxN];
vector<int> rig[mxN];
vector<item> gg[mxN];
multiset<pair<ll, int>> ms[mxN];
int timer = 0;
void dfs_sz(int u, int p)
{
sub[u] = 1;
for(auto it : adj[u]) {
int v = it.fi;
if(v == p || removed[v] == true) continue;
dfs_sz(v, u);
sub[u] += sub[v];
}
}
int find_centroid(int u, int p, int n)
{
for(auto it : adj[u]) {
int v = it.fi;
if(v == p || removed[v] == true) continue;
if(sub[v] > n / 2) return find_centroid(v, u, n);
}
return u;
}
void dfs(int u, int p, int root, ll cur, int group)
{
lef[u].pb(++timer);
seg[root].update(timer, timer, cur);
for(auto it : adj[u]) {
int v = it.fi;
ll c = it.se;
if(v == p || removed[v] == true) continue;
if(u == root) dfs(v, u, root, cur + c, v);
else dfs(v, u, root, cur + c, group);
}
rig[u].pb(timer);
}
void dfs_gg(int u, int p, int _ll, int rr, int g)
{
gg[u].pb({_ll, rr, g});
for(auto it : adj[u]) {
int v = it.fi;
if(v == p || removed[v] == true) continue;
if(p == -1) dfs_gg(v, u, lef[v].back(), rig[v].back(), v);
else dfs_gg(v, u, _ll, rr, g);
}
}
void update_maxval(int p)
{
ll val = 0;
if(sz(ms[p]) == 1) {
pair<ll, int> tmp = *ms[p].begin();
val = tmp.fi;
}
if(sz(ms[p]) > 1) {
auto it = ms[p].end();
--it;
pair<ll, int> tmp;
tmp = *it;
val += tmp.fi;
--it;
tmp = *it;
val += tmp.fi;
}
// cout << p << ' ' << val << endl;
maxval.update(p, val);
}
void init_centroid(int u, int p)
{
timer = 0;
dfs_sz(u, -1);
int c = find_centroid(u, -1, sub[u]);
par[c] = p;
if(p != -1) depth[c] = depth[p] + 1;
else depth[c] = 0;
seg[c] = IT(sub[u]);
dfs(c, -1, c, 0, 0);
dfs_gg(c, -1, 0, 0, 0);
for(auto it : adj[c]) {
int v = it.fi;
if(removed[v] == false) {
int l = lef[v].back();
int r = rig[v].back();
ll val = seg[c].getmax(l, r);
ms[c].insert(make_pair(val, v));
}
}
update_maxval(c);
removed[c] = true;
for(auto it : adj[c]) {
int v = it.fi;
if(removed[v] == true) continue;;
init_centroid(v, c);
}
}
void update(int u, int v, ll w)
{
int x = u;
int y = v;
int id1 = 0;
int id2 = 0;
while(x != y)
{
if(depth[x] > depth[y]) {
x = par[x];
++id1;
}
else {
y = par[y];
++id2;
}
}
while(x != -1) {
int lu = lef[u][id1];
int ru = rig[u][id1];
int lv = lef[v][id2];
int rv = rig[v][id2];
if(lu <= lv && rv <= ru) {
int _ll = gg[v][id2]._ll;
int rr = gg[v][id2].rr;
int cc = gg[v][id2].cc;
ll val = seg[x].getmax(_ll, rr);
ms[x].erase(ms[x].find(make_pair(val, cc)));
seg[x].update(lv, rv, w);
val = seg[x].getmax(_ll, rr);
ms[x].insert(make_pair(val, cc));
}
if(lv <= lu && ru <= rv) {
int _ll = gg[u][id1]._ll;
int rr = gg[u][id1].rr;
int cc = gg[u][id1].cc;
ll val = seg[x].getmax(_ll, rr);
ms[x].erase(ms[x].find(make_pair(val, cc)));
seg[x].update(lu, ru, w);
val = seg[x].getmax(_ll, rr);
ms[x].insert(make_pair(val, cc));
}
update_maxval(x);
x = par[x];
++id1;
++id2;
}
}
void solve()
{
cin >> n >> q >> lim;
for(int i = 1; i < n; i++) {
int u, v;
ll c;
cin >> u >> v >> c;
adj[u].pb({v, c});
adj[v].pb({u, c});
eddd[i] = {u, v, c};
}
maxval = ITmax(n);
init_centroid(1, -1);
for(int i = 1; i <= n; i++) {
reverse(all(lef[i]));
reverse(all(rig[i]));
reverse(all(gg[i]));
}
// cout << maxval.getmax(1, n) << endl;
// return;
ll last = 0;
while(q--) {
ll idx;
ll w;
cin >> idx >> w;
idx = (idx + last) % (n - 1);
w = (w + last) % lim;
// cout << idx << ' ' << w << endl;
update(eddd[idx + 1].u, eddd[idx + 1].v, w - eddd[idx + 1].c);
eddd[idx + 1].c = w;
// update(eddd[idx + 1].u, eddd[idx + 1].v, eddd[idx + 1].c);
last = maxval.getmax(1, n);
cout << last << endl;
}
// for(int i = 1; i < n; i++) cout << eddd[i].u << ' ' << eddd[i].v << ' ' << eddd[i].c << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("task.inp" , "r" , stdin);
// freopen(TASK".out" , "w" , stdout);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19916 KB |
Output is correct |
2 |
Correct |
10 ms |
19944 KB |
Output is correct |
3 |
Correct |
10 ms |
19860 KB |
Output is correct |
4 |
Correct |
11 ms |
19924 KB |
Output is correct |
5 |
Correct |
11 ms |
19924 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
13 ms |
19924 KB |
Output is correct |
8 |
Correct |
13 ms |
19932 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19968 KB |
Output is correct |
11 |
Correct |
11 ms |
19924 KB |
Output is correct |
12 |
Correct |
11 ms |
19984 KB |
Output is correct |
13 |
Correct |
11 ms |
19936 KB |
Output is correct |
14 |
Correct |
12 ms |
19948 KB |
Output is correct |
15 |
Correct |
11 ms |
19924 KB |
Output is correct |
16 |
Correct |
10 ms |
19940 KB |
Output is correct |
17 |
Correct |
11 ms |
19940 KB |
Output is correct |
18 |
Correct |
14 ms |
20004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19916 KB |
Output is correct |
2 |
Correct |
10 ms |
19944 KB |
Output is correct |
3 |
Correct |
10 ms |
19860 KB |
Output is correct |
4 |
Correct |
11 ms |
19924 KB |
Output is correct |
5 |
Correct |
11 ms |
19924 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
13 ms |
19924 KB |
Output is correct |
8 |
Correct |
13 ms |
19932 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19968 KB |
Output is correct |
11 |
Correct |
11 ms |
19924 KB |
Output is correct |
12 |
Correct |
11 ms |
19984 KB |
Output is correct |
13 |
Correct |
11 ms |
19936 KB |
Output is correct |
14 |
Correct |
12 ms |
19948 KB |
Output is correct |
15 |
Correct |
11 ms |
19924 KB |
Output is correct |
16 |
Correct |
10 ms |
19940 KB |
Output is correct |
17 |
Correct |
11 ms |
19940 KB |
Output is correct |
18 |
Correct |
14 ms |
20004 KB |
Output is correct |
19 |
Correct |
32 ms |
20820 KB |
Output is correct |
20 |
Correct |
34 ms |
20944 KB |
Output is correct |
21 |
Correct |
32 ms |
21076 KB |
Output is correct |
22 |
Correct |
31 ms |
21296 KB |
Output is correct |
23 |
Correct |
49 ms |
24772 KB |
Output is correct |
24 |
Correct |
57 ms |
25864 KB |
Output is correct |
25 |
Correct |
63 ms |
26524 KB |
Output is correct |
26 |
Correct |
60 ms |
27276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19924 KB |
Output is correct |
2 |
Correct |
10 ms |
19940 KB |
Output is correct |
3 |
Correct |
11 ms |
19924 KB |
Output is correct |
4 |
Correct |
20 ms |
20104 KB |
Output is correct |
5 |
Correct |
60 ms |
21068 KB |
Output is correct |
6 |
Correct |
12 ms |
19924 KB |
Output is correct |
7 |
Correct |
10 ms |
20132 KB |
Output is correct |
8 |
Correct |
10 ms |
20196 KB |
Output is correct |
9 |
Correct |
12 ms |
20336 KB |
Output is correct |
10 |
Correct |
27 ms |
20468 KB |
Output is correct |
11 |
Correct |
91 ms |
21444 KB |
Output is correct |
12 |
Correct |
17 ms |
22484 KB |
Output is correct |
13 |
Correct |
18 ms |
22508 KB |
Output is correct |
14 |
Correct |
19 ms |
22552 KB |
Output is correct |
15 |
Correct |
45 ms |
22876 KB |
Output is correct |
16 |
Correct |
120 ms |
23980 KB |
Output is correct |
17 |
Correct |
168 ms |
72652 KB |
Output is correct |
18 |
Correct |
164 ms |
72504 KB |
Output is correct |
19 |
Correct |
183 ms |
72564 KB |
Output is correct |
20 |
Correct |
201 ms |
72808 KB |
Output is correct |
21 |
Correct |
469 ms |
74164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
21076 KB |
Output is correct |
2 |
Correct |
37 ms |
21204 KB |
Output is correct |
3 |
Correct |
120 ms |
21716 KB |
Output is correct |
4 |
Correct |
218 ms |
22372 KB |
Output is correct |
5 |
Correct |
53 ms |
33796 KB |
Output is correct |
6 |
Correct |
84 ms |
33868 KB |
Output is correct |
7 |
Correct |
230 ms |
34576 KB |
Output is correct |
8 |
Correct |
449 ms |
35392 KB |
Output is correct |
9 |
Correct |
274 ms |
96952 KB |
Output is correct |
10 |
Correct |
289 ms |
97200 KB |
Output is correct |
11 |
Correct |
621 ms |
97760 KB |
Output is correct |
12 |
Correct |
880 ms |
98684 KB |
Output is correct |
13 |
Correct |
549 ms |
180528 KB |
Output is correct |
14 |
Correct |
586 ms |
180600 KB |
Output is correct |
15 |
Correct |
979 ms |
181376 KB |
Output is correct |
16 |
Correct |
1373 ms |
182144 KB |
Output is correct |
17 |
Correct |
1824 ms |
181976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2112 ms |
158508 KB |
Output is correct |
2 |
Correct |
2297 ms |
161576 KB |
Output is correct |
3 |
Correct |
2270 ms |
160456 KB |
Output is correct |
4 |
Correct |
2194 ms |
161056 KB |
Output is correct |
5 |
Correct |
2232 ms |
154500 KB |
Output is correct |
6 |
Correct |
1854 ms |
120472 KB |
Output is correct |
7 |
Correct |
2776 ms |
189760 KB |
Output is correct |
8 |
Correct |
2877 ms |
189776 KB |
Output is correct |
9 |
Correct |
2857 ms |
189664 KB |
Output is correct |
10 |
Correct |
2816 ms |
188796 KB |
Output is correct |
11 |
Correct |
2757 ms |
181036 KB |
Output is correct |
12 |
Correct |
2485 ms |
138164 KB |
Output is correct |
13 |
Correct |
2801 ms |
210808 KB |
Output is correct |
14 |
Correct |
2704 ms |
210668 KB |
Output is correct |
15 |
Correct |
2729 ms |
210600 KB |
Output is correct |
16 |
Correct |
2791 ms |
209900 KB |
Output is correct |
17 |
Correct |
2731 ms |
200600 KB |
Output is correct |
18 |
Correct |
2212 ms |
148068 KB |
Output is correct |
19 |
Correct |
2791 ms |
210624 KB |
Output is correct |
20 |
Correct |
2872 ms |
210764 KB |
Output is correct |
21 |
Correct |
2773 ms |
210764 KB |
Output is correct |
22 |
Correct |
2690 ms |
210012 KB |
Output is correct |
23 |
Correct |
2593 ms |
200804 KB |
Output is correct |
24 |
Correct |
2230 ms |
147984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19916 KB |
Output is correct |
2 |
Correct |
10 ms |
19944 KB |
Output is correct |
3 |
Correct |
10 ms |
19860 KB |
Output is correct |
4 |
Correct |
11 ms |
19924 KB |
Output is correct |
5 |
Correct |
11 ms |
19924 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
13 ms |
19924 KB |
Output is correct |
8 |
Correct |
13 ms |
19932 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19968 KB |
Output is correct |
11 |
Correct |
11 ms |
19924 KB |
Output is correct |
12 |
Correct |
11 ms |
19984 KB |
Output is correct |
13 |
Correct |
11 ms |
19936 KB |
Output is correct |
14 |
Correct |
12 ms |
19948 KB |
Output is correct |
15 |
Correct |
11 ms |
19924 KB |
Output is correct |
16 |
Correct |
10 ms |
19940 KB |
Output is correct |
17 |
Correct |
11 ms |
19940 KB |
Output is correct |
18 |
Correct |
14 ms |
20004 KB |
Output is correct |
19 |
Correct |
32 ms |
20820 KB |
Output is correct |
20 |
Correct |
34 ms |
20944 KB |
Output is correct |
21 |
Correct |
32 ms |
21076 KB |
Output is correct |
22 |
Correct |
31 ms |
21296 KB |
Output is correct |
23 |
Correct |
49 ms |
24772 KB |
Output is correct |
24 |
Correct |
57 ms |
25864 KB |
Output is correct |
25 |
Correct |
63 ms |
26524 KB |
Output is correct |
26 |
Correct |
60 ms |
27276 KB |
Output is correct |
27 |
Correct |
10 ms |
19924 KB |
Output is correct |
28 |
Correct |
10 ms |
19940 KB |
Output is correct |
29 |
Correct |
11 ms |
19924 KB |
Output is correct |
30 |
Correct |
20 ms |
20104 KB |
Output is correct |
31 |
Correct |
60 ms |
21068 KB |
Output is correct |
32 |
Correct |
12 ms |
19924 KB |
Output is correct |
33 |
Correct |
10 ms |
20132 KB |
Output is correct |
34 |
Correct |
10 ms |
20196 KB |
Output is correct |
35 |
Correct |
12 ms |
20336 KB |
Output is correct |
36 |
Correct |
27 ms |
20468 KB |
Output is correct |
37 |
Correct |
91 ms |
21444 KB |
Output is correct |
38 |
Correct |
17 ms |
22484 KB |
Output is correct |
39 |
Correct |
18 ms |
22508 KB |
Output is correct |
40 |
Correct |
19 ms |
22552 KB |
Output is correct |
41 |
Correct |
45 ms |
22876 KB |
Output is correct |
42 |
Correct |
120 ms |
23980 KB |
Output is correct |
43 |
Correct |
168 ms |
72652 KB |
Output is correct |
44 |
Correct |
164 ms |
72504 KB |
Output is correct |
45 |
Correct |
183 ms |
72564 KB |
Output is correct |
46 |
Correct |
201 ms |
72808 KB |
Output is correct |
47 |
Correct |
469 ms |
74164 KB |
Output is correct |
48 |
Correct |
20 ms |
21076 KB |
Output is correct |
49 |
Correct |
37 ms |
21204 KB |
Output is correct |
50 |
Correct |
120 ms |
21716 KB |
Output is correct |
51 |
Correct |
218 ms |
22372 KB |
Output is correct |
52 |
Correct |
53 ms |
33796 KB |
Output is correct |
53 |
Correct |
84 ms |
33868 KB |
Output is correct |
54 |
Correct |
230 ms |
34576 KB |
Output is correct |
55 |
Correct |
449 ms |
35392 KB |
Output is correct |
56 |
Correct |
274 ms |
96952 KB |
Output is correct |
57 |
Correct |
289 ms |
97200 KB |
Output is correct |
58 |
Correct |
621 ms |
97760 KB |
Output is correct |
59 |
Correct |
880 ms |
98684 KB |
Output is correct |
60 |
Correct |
549 ms |
180528 KB |
Output is correct |
61 |
Correct |
586 ms |
180600 KB |
Output is correct |
62 |
Correct |
979 ms |
181376 KB |
Output is correct |
63 |
Correct |
1373 ms |
182144 KB |
Output is correct |
64 |
Correct |
1824 ms |
181976 KB |
Output is correct |
65 |
Correct |
2112 ms |
158508 KB |
Output is correct |
66 |
Correct |
2297 ms |
161576 KB |
Output is correct |
67 |
Correct |
2270 ms |
160456 KB |
Output is correct |
68 |
Correct |
2194 ms |
161056 KB |
Output is correct |
69 |
Correct |
2232 ms |
154500 KB |
Output is correct |
70 |
Correct |
1854 ms |
120472 KB |
Output is correct |
71 |
Correct |
2776 ms |
189760 KB |
Output is correct |
72 |
Correct |
2877 ms |
189776 KB |
Output is correct |
73 |
Correct |
2857 ms |
189664 KB |
Output is correct |
74 |
Correct |
2816 ms |
188796 KB |
Output is correct |
75 |
Correct |
2757 ms |
181036 KB |
Output is correct |
76 |
Correct |
2485 ms |
138164 KB |
Output is correct |
77 |
Correct |
2801 ms |
210808 KB |
Output is correct |
78 |
Correct |
2704 ms |
210668 KB |
Output is correct |
79 |
Correct |
2729 ms |
210600 KB |
Output is correct |
80 |
Correct |
2791 ms |
209900 KB |
Output is correct |
81 |
Correct |
2731 ms |
200600 KB |
Output is correct |
82 |
Correct |
2212 ms |
148068 KB |
Output is correct |
83 |
Correct |
2791 ms |
210624 KB |
Output is correct |
84 |
Correct |
2872 ms |
210764 KB |
Output is correct |
85 |
Correct |
2773 ms |
210764 KB |
Output is correct |
86 |
Correct |
2690 ms |
210012 KB |
Output is correct |
87 |
Correct |
2593 ms |
200804 KB |
Output is correct |
88 |
Correct |
2230 ms |
147984 KB |
Output is correct |
89 |
Correct |
2095 ms |
158980 KB |
Output is correct |
90 |
Correct |
2350 ms |
169304 KB |
Output is correct |
91 |
Correct |
2707 ms |
183544 KB |
Output is correct |
92 |
Correct |
2788 ms |
188720 KB |
Output is correct |
93 |
Correct |
2831 ms |
195968 KB |
Output is correct |
94 |
Correct |
2703 ms |
202384 KB |
Output is correct |
95 |
Correct |
2681 ms |
210020 KB |
Output is correct |
96 |
Correct |
2653 ms |
210132 KB |
Output is correct |
97 |
Correct |
2665 ms |
210048 KB |
Output is correct |
98 |
Correct |
2624 ms |
210092 KB |
Output is correct |
99 |
Correct |
2698 ms |
209972 KB |
Output is correct |
100 |
Correct |
2599 ms |
210052 KB |
Output is correct |