#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2,fma")
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
#ifdef LOCAL
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1);
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()
const long long inf = 1e18;
cl mod = 1e9 + 7, MOD = 998244353;
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
return out << '(' << a.first << ", " << a.second << ')'; }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;
cl N = 1e5 + 7;
ll tin [N], tout [N], e1 [N], e2 [N], W [N];
vector <ll> adj [N], walk;
void dfs (ll v = 1, ll par = 0) {
walk.push_back(v);
tin[v] = SZ(walk);
for (auto u : adj[v]) if (u != par) {
dfs(u, v);
walk.push_back(v);
}
walk.push_back(v);
tout[v] = SZ(walk);
}
struct node
{
ll m, M, Mm, mM, ans;
friend node operator + (const node &x, const node &y) {
return {min(x.m, y.m), max(x.M, y.M), max({x.Mm, y.Mm, x.M - 2 * y.m}), max({x.mM, y.mM, y.M - 2 * x.m}), max({x.ans, y.ans, x.Mm + y.M, x.M + y.mM})};
}
};
struct seg
{
node n;
ll lz, l, r;
seg *lt, *rt;
seg (ll L = 1, ll R = SZ(walk)) {
n = {0, 0, 0, 0, 0};
lz = 0, l = L, r = R;
}
void build () {
if (l == r) return;
lt = new seg (l, mid);
rt = new seg (mid + 1, r);
lt->build();
rt->build();
}
inline void push (ll x) { n.m += x; n.M += x; n.Mm -= x; n.mM -= x; lz += x; }
inline void shift () { lt->push(lz); rt->push(lz); lz = 0; }
void upd (ll ql, ll qr, ll x) {
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
push(x);
return;
}
shift();
lt->upd(ql, qr, x);
rt->upd(ql, qr, x);
n = lt->n + rt->n;
}
} mytree;
int main ()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n, q, mx_w, i, ans = 0, x, y;
cin>> n >> q >> mx_w;
for (i = 1; i < n; i++) {
cin>> e1[i] >> e2[i] >> W[i];
adj[e1[i]].push_back(e2[i]);
adj[e2[i]].push_back(e1[i]);
}
dfs();
mytree.r = SZ(walk);
mytree.build();
for (i = 1; i < n; i++) {
if (tin[e1[i]] > tin[e2[i]]) swap(e1[i], e2[i]);
mytree.upd(tin[e2[i]], tout[e2[i]], W[i]);
}
while (q--) {
cin>> x >> y;
x = (x + ans) % (n-1) + 1;
y = (y + ans) % mx_w;
mytree.upd(tin[e2[x]], tout[e2[x]], y - W[x]);
W[x] = y;
cout<< (ans = mytree.n.ans) << '\n';
}
cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
*/
Compilation message
diameter.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
diameter.cpp:42:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
42 | if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']'; }
| ^~
diameter.cpp:42:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
42 | if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']'; }
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2668 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
2 ms |
2796 KB |
Output is correct |
8 |
Correct |
2 ms |
2796 KB |
Output is correct |
9 |
Correct |
2 ms |
2796 KB |
Output is correct |
10 |
Correct |
2 ms |
2796 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2796 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
2 ms |
2796 KB |
Output is correct |
15 |
Correct |
2 ms |
2796 KB |
Output is correct |
16 |
Correct |
3 ms |
2796 KB |
Output is correct |
17 |
Correct |
2 ms |
2796 KB |
Output is correct |
18 |
Correct |
3 ms |
2796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2668 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
2 ms |
2796 KB |
Output is correct |
8 |
Correct |
2 ms |
2796 KB |
Output is correct |
9 |
Correct |
2 ms |
2796 KB |
Output is correct |
10 |
Correct |
2 ms |
2796 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2796 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
2 ms |
2796 KB |
Output is correct |
15 |
Correct |
2 ms |
2796 KB |
Output is correct |
16 |
Correct |
3 ms |
2796 KB |
Output is correct |
17 |
Correct |
2 ms |
2796 KB |
Output is correct |
18 |
Correct |
3 ms |
2796 KB |
Output is correct |
19 |
Correct |
7 ms |
3436 KB |
Output is correct |
20 |
Correct |
7 ms |
3436 KB |
Output is correct |
21 |
Correct |
7 ms |
3436 KB |
Output is correct |
22 |
Correct |
12 ms |
3520 KB |
Output is correct |
23 |
Correct |
14 ms |
6252 KB |
Output is correct |
24 |
Correct |
15 ms |
6272 KB |
Output is correct |
25 |
Correct |
15 ms |
6252 KB |
Output is correct |
26 |
Correct |
17 ms |
6508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
3 ms |
2796 KB |
Output is correct |
4 |
Correct |
11 ms |
3052 KB |
Output is correct |
5 |
Correct |
44 ms |
3936 KB |
Output is correct |
6 |
Correct |
2 ms |
2668 KB |
Output is correct |
7 |
Correct |
3 ms |
3052 KB |
Output is correct |
8 |
Correct |
3 ms |
3052 KB |
Output is correct |
9 |
Correct |
4 ms |
3052 KB |
Output is correct |
10 |
Correct |
14 ms |
3308 KB |
Output is correct |
11 |
Correct |
60 ms |
4460 KB |
Output is correct |
12 |
Correct |
8 ms |
6124 KB |
Output is correct |
13 |
Correct |
9 ms |
6124 KB |
Output is correct |
14 |
Correct |
10 ms |
6124 KB |
Output is correct |
15 |
Correct |
24 ms |
6380 KB |
Output is correct |
16 |
Correct |
81 ms |
7532 KB |
Output is correct |
17 |
Correct |
164 ms |
70488 KB |
Output is correct |
18 |
Correct |
131 ms |
70488 KB |
Output is correct |
19 |
Correct |
135 ms |
70616 KB |
Output is correct |
20 |
Correct |
162 ms |
70744 KB |
Output is correct |
21 |
Correct |
296 ms |
72152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3436 KB |
Output is correct |
2 |
Correct |
11 ms |
3564 KB |
Output is correct |
3 |
Correct |
39 ms |
4076 KB |
Output is correct |
4 |
Correct |
74 ms |
4844 KB |
Output is correct |
5 |
Correct |
17 ms |
9580 KB |
Output is correct |
6 |
Correct |
28 ms |
9708 KB |
Output is correct |
7 |
Correct |
73 ms |
10348 KB |
Output is correct |
8 |
Correct |
118 ms |
11116 KB |
Output is correct |
9 |
Correct |
93 ms |
36984 KB |
Output is correct |
10 |
Correct |
96 ms |
36964 KB |
Output is correct |
11 |
Correct |
154 ms |
37604 KB |
Output is correct |
12 |
Correct |
224 ms |
38500 KB |
Output is correct |
13 |
Correct |
158 ms |
70868 KB |
Output is correct |
14 |
Correct |
185 ms |
71128 KB |
Output is correct |
15 |
Correct |
261 ms |
71892 KB |
Output is correct |
16 |
Correct |
321 ms |
72532 KB |
Output is correct |
17 |
Correct |
341 ms |
72276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
454 ms |
74836 KB |
Output is correct |
2 |
Correct |
474 ms |
74836 KB |
Output is correct |
3 |
Correct |
447 ms |
74708 KB |
Output is correct |
4 |
Correct |
492 ms |
74724 KB |
Output is correct |
5 |
Correct |
442 ms |
74888 KB |
Output is correct |
6 |
Correct |
401 ms |
74836 KB |
Output is correct |
7 |
Correct |
505 ms |
77092 KB |
Output is correct |
8 |
Correct |
517 ms |
77016 KB |
Output is correct |
9 |
Correct |
521 ms |
77020 KB |
Output is correct |
10 |
Correct |
556 ms |
76988 KB |
Output is correct |
11 |
Correct |
482 ms |
76888 KB |
Output is correct |
12 |
Correct |
433 ms |
76628 KB |
Output is correct |
13 |
Correct |
630 ms |
80300 KB |
Output is correct |
14 |
Correct |
600 ms |
80468 KB |
Output is correct |
15 |
Correct |
608 ms |
80316 KB |
Output is correct |
16 |
Correct |
587 ms |
80472 KB |
Output is correct |
17 |
Correct |
587 ms |
79904 KB |
Output is correct |
18 |
Correct |
512 ms |
77656 KB |
Output is correct |
19 |
Correct |
610 ms |
80340 KB |
Output is correct |
20 |
Correct |
588 ms |
80212 KB |
Output is correct |
21 |
Correct |
583 ms |
80524 KB |
Output is correct |
22 |
Correct |
616 ms |
80392 KB |
Output is correct |
23 |
Correct |
587 ms |
79828 KB |
Output is correct |
24 |
Correct |
484 ms |
77828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2668 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
2 ms |
2796 KB |
Output is correct |
8 |
Correct |
2 ms |
2796 KB |
Output is correct |
9 |
Correct |
2 ms |
2796 KB |
Output is correct |
10 |
Correct |
2 ms |
2796 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2796 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
2 ms |
2796 KB |
Output is correct |
15 |
Correct |
2 ms |
2796 KB |
Output is correct |
16 |
Correct |
3 ms |
2796 KB |
Output is correct |
17 |
Correct |
2 ms |
2796 KB |
Output is correct |
18 |
Correct |
3 ms |
2796 KB |
Output is correct |
19 |
Correct |
7 ms |
3436 KB |
Output is correct |
20 |
Correct |
7 ms |
3436 KB |
Output is correct |
21 |
Correct |
7 ms |
3436 KB |
Output is correct |
22 |
Correct |
12 ms |
3520 KB |
Output is correct |
23 |
Correct |
14 ms |
6252 KB |
Output is correct |
24 |
Correct |
15 ms |
6272 KB |
Output is correct |
25 |
Correct |
15 ms |
6252 KB |
Output is correct |
26 |
Correct |
17 ms |
6508 KB |
Output is correct |
27 |
Correct |
2 ms |
2668 KB |
Output is correct |
28 |
Correct |
2 ms |
2668 KB |
Output is correct |
29 |
Correct |
3 ms |
2796 KB |
Output is correct |
30 |
Correct |
11 ms |
3052 KB |
Output is correct |
31 |
Correct |
44 ms |
3936 KB |
Output is correct |
32 |
Correct |
2 ms |
2668 KB |
Output is correct |
33 |
Correct |
3 ms |
3052 KB |
Output is correct |
34 |
Correct |
3 ms |
3052 KB |
Output is correct |
35 |
Correct |
4 ms |
3052 KB |
Output is correct |
36 |
Correct |
14 ms |
3308 KB |
Output is correct |
37 |
Correct |
60 ms |
4460 KB |
Output is correct |
38 |
Correct |
8 ms |
6124 KB |
Output is correct |
39 |
Correct |
9 ms |
6124 KB |
Output is correct |
40 |
Correct |
10 ms |
6124 KB |
Output is correct |
41 |
Correct |
24 ms |
6380 KB |
Output is correct |
42 |
Correct |
81 ms |
7532 KB |
Output is correct |
43 |
Correct |
164 ms |
70488 KB |
Output is correct |
44 |
Correct |
131 ms |
70488 KB |
Output is correct |
45 |
Correct |
135 ms |
70616 KB |
Output is correct |
46 |
Correct |
162 ms |
70744 KB |
Output is correct |
47 |
Correct |
296 ms |
72152 KB |
Output is correct |
48 |
Correct |
5 ms |
3436 KB |
Output is correct |
49 |
Correct |
11 ms |
3564 KB |
Output is correct |
50 |
Correct |
39 ms |
4076 KB |
Output is correct |
51 |
Correct |
74 ms |
4844 KB |
Output is correct |
52 |
Correct |
17 ms |
9580 KB |
Output is correct |
53 |
Correct |
28 ms |
9708 KB |
Output is correct |
54 |
Correct |
73 ms |
10348 KB |
Output is correct |
55 |
Correct |
118 ms |
11116 KB |
Output is correct |
56 |
Correct |
93 ms |
36984 KB |
Output is correct |
57 |
Correct |
96 ms |
36964 KB |
Output is correct |
58 |
Correct |
154 ms |
37604 KB |
Output is correct |
59 |
Correct |
224 ms |
38500 KB |
Output is correct |
60 |
Correct |
158 ms |
70868 KB |
Output is correct |
61 |
Correct |
185 ms |
71128 KB |
Output is correct |
62 |
Correct |
261 ms |
71892 KB |
Output is correct |
63 |
Correct |
321 ms |
72532 KB |
Output is correct |
64 |
Correct |
341 ms |
72276 KB |
Output is correct |
65 |
Correct |
454 ms |
74836 KB |
Output is correct |
66 |
Correct |
474 ms |
74836 KB |
Output is correct |
67 |
Correct |
447 ms |
74708 KB |
Output is correct |
68 |
Correct |
492 ms |
74724 KB |
Output is correct |
69 |
Correct |
442 ms |
74888 KB |
Output is correct |
70 |
Correct |
401 ms |
74836 KB |
Output is correct |
71 |
Correct |
505 ms |
77092 KB |
Output is correct |
72 |
Correct |
517 ms |
77016 KB |
Output is correct |
73 |
Correct |
521 ms |
77020 KB |
Output is correct |
74 |
Correct |
556 ms |
76988 KB |
Output is correct |
75 |
Correct |
482 ms |
76888 KB |
Output is correct |
76 |
Correct |
433 ms |
76628 KB |
Output is correct |
77 |
Correct |
630 ms |
80300 KB |
Output is correct |
78 |
Correct |
600 ms |
80468 KB |
Output is correct |
79 |
Correct |
608 ms |
80316 KB |
Output is correct |
80 |
Correct |
587 ms |
80472 KB |
Output is correct |
81 |
Correct |
587 ms |
79904 KB |
Output is correct |
82 |
Correct |
512 ms |
77656 KB |
Output is correct |
83 |
Correct |
610 ms |
80340 KB |
Output is correct |
84 |
Correct |
588 ms |
80212 KB |
Output is correct |
85 |
Correct |
583 ms |
80524 KB |
Output is correct |
86 |
Correct |
616 ms |
80392 KB |
Output is correct |
87 |
Correct |
587 ms |
79828 KB |
Output is correct |
88 |
Correct |
484 ms |
77828 KB |
Output is correct |
89 |
Correct |
456 ms |
73812 KB |
Output is correct |
90 |
Correct |
442 ms |
74052 KB |
Output is correct |
91 |
Correct |
507 ms |
75348 KB |
Output is correct |
92 |
Correct |
510 ms |
75228 KB |
Output is correct |
93 |
Correct |
593 ms |
77524 KB |
Output is correct |
94 |
Correct |
539 ms |
76500 KB |
Output is correct |
95 |
Correct |
613 ms |
77944 KB |
Output is correct |
96 |
Correct |
624 ms |
77012 KB |
Output is correct |
97 |
Correct |
582 ms |
77652 KB |
Output is correct |
98 |
Correct |
595 ms |
79560 KB |
Output is correct |
99 |
Correct |
584 ms |
77396 KB |
Output is correct |
100 |
Correct |
590 ms |
77512 KB |
Output is correct |