//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) {
stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) {
string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
bool fst = 1; string res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += to_string(x);
}
res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e5 + 10;
const ll INF = 4e18;
int n, q, down[MAXN], st[MAXN], ft[MAXN], T;
ll tw[MAXN], w[MAXN], W;
vector<pair<int, int>> adj[MAXN];
struct Node {
ll dp[4][4], lazy;
Node (ll x = 0) {
fill(&dp[0][0], &dp[3][3], x);
for (int i = 0; i < 4; i++) {
dp[i][i] = 0;
}
lazy = 0;
}
} seg[MAXN << 2];
inline Node merge (const Node& x, const Node& y) {
Node res(-INF);
for (int i = 0; i < 4; i++) {
for (int j = i; j < 4; j++) {
for (int k = i; k <= j; k++) {
res.dp[i][j] = max(res.dp[i][j], x.dp[i][k] + y.dp[k][j]);
}
}
}
return res;
}
void dfs (int v, int p) {
st[v] = T++;
for (auto [u, i] : adj[v]) {
if (u == p) {
continue;
}
down[i] = u;
w[u] = tw[i];
dfs(u, v);
T++;
}
ft[v] = T;
}
inline void update (int nd, ll x) {
auto cof = [&](int l, int r) {
int ret = 0;
if (l < 1 && 1 <= r) {
ret++;
}
if (l < 2 && 2 <= r) {
ret -= 2;
}
if (l < 3 && 3 <= r) {
ret++;
}
return ret;
};
for (int i = 0; i < 4; i++) {
for (int j = i; j < 4; j++) {
seg[nd].dp[i][j] += x * cof(i, j);
}
}
seg[nd].lazy += x;
}
inline void shift (int nd) {
int L = nd << 1, R = L | 1;
update(L, seg[nd].lazy);
update(R, seg[nd].lazy);
seg[nd].lazy = 0;
}
void add (int nd, int cl, int cr, int l, int r, ll x) {
if (cl == l && cr == r) {
update(nd, x);
return;
}
shift(nd);
int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1;
if (l < mid) {
add(L, cl, mid, l, min(r, mid), x);
}
if (r > mid) {
add(R, mid, cr, max(mid, l), r, x);
}
seg[nd] = merge(seg[L], seg[R]);
}
inline void add (int l, int r, ll x) {
add(1, 0, T, l, r, x);
}
int main() {
ios::sync_with_stdio(0);
#ifndef LOCAL
cin.tie(0);
#endif
cin >> n >> q >> W;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v >> tw[i];
u--, v--;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
dfs(0, -1);
for (int i = 0; i < n - 1; i++) {
int v = down[i];
add(st[v], ft[v], w[v]);
}
ll last = 0;
while (q--) {
int e;
ll x;
cin >> e >> x;
e = (e + last) % (n - 1);
x = (x + last) % W;
int v = down[e];
add(st[v], ft[v], x - w[v]);
w[v] = x;
last = seg[1].dp[0][3];
cout << last << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
111420 KB |
Output is correct |
2 |
Correct |
60 ms |
111504 KB |
Output is correct |
3 |
Correct |
54 ms |
111416 KB |
Output is correct |
4 |
Correct |
50 ms |
111456 KB |
Output is correct |
5 |
Correct |
50 ms |
111388 KB |
Output is correct |
6 |
Correct |
54 ms |
111436 KB |
Output is correct |
7 |
Correct |
63 ms |
111440 KB |
Output is correct |
8 |
Correct |
71 ms |
111380 KB |
Output is correct |
9 |
Correct |
67 ms |
111420 KB |
Output is correct |
10 |
Correct |
53 ms |
111396 KB |
Output is correct |
11 |
Correct |
51 ms |
111440 KB |
Output is correct |
12 |
Correct |
54 ms |
111416 KB |
Output is correct |
13 |
Correct |
82 ms |
111392 KB |
Output is correct |
14 |
Correct |
57 ms |
111420 KB |
Output is correct |
15 |
Correct |
53 ms |
111380 KB |
Output is correct |
16 |
Correct |
73 ms |
111372 KB |
Output is correct |
17 |
Correct |
50 ms |
111564 KB |
Output is correct |
18 |
Correct |
47 ms |
111432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
111420 KB |
Output is correct |
2 |
Correct |
60 ms |
111504 KB |
Output is correct |
3 |
Correct |
54 ms |
111416 KB |
Output is correct |
4 |
Correct |
50 ms |
111456 KB |
Output is correct |
5 |
Correct |
50 ms |
111388 KB |
Output is correct |
6 |
Correct |
54 ms |
111436 KB |
Output is correct |
7 |
Correct |
63 ms |
111440 KB |
Output is correct |
8 |
Correct |
71 ms |
111380 KB |
Output is correct |
9 |
Correct |
67 ms |
111420 KB |
Output is correct |
10 |
Correct |
53 ms |
111396 KB |
Output is correct |
11 |
Correct |
51 ms |
111440 KB |
Output is correct |
12 |
Correct |
54 ms |
111416 KB |
Output is correct |
13 |
Correct |
82 ms |
111392 KB |
Output is correct |
14 |
Correct |
57 ms |
111420 KB |
Output is correct |
15 |
Correct |
53 ms |
111380 KB |
Output is correct |
16 |
Correct |
73 ms |
111372 KB |
Output is correct |
17 |
Correct |
50 ms |
111564 KB |
Output is correct |
18 |
Correct |
47 ms |
111432 KB |
Output is correct |
19 |
Correct |
68 ms |
111596 KB |
Output is correct |
20 |
Correct |
82 ms |
111580 KB |
Output is correct |
21 |
Correct |
75 ms |
111588 KB |
Output is correct |
22 |
Correct |
69 ms |
111604 KB |
Output is correct |
23 |
Correct |
114 ms |
111868 KB |
Output is correct |
24 |
Correct |
94 ms |
111944 KB |
Output is correct |
25 |
Correct |
77 ms |
111908 KB |
Output is correct |
26 |
Correct |
79 ms |
112240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
111476 KB |
Output is correct |
2 |
Correct |
55 ms |
111472 KB |
Output is correct |
3 |
Correct |
72 ms |
111504 KB |
Output is correct |
4 |
Correct |
87 ms |
111624 KB |
Output is correct |
5 |
Correct |
155 ms |
112652 KB |
Output is correct |
6 |
Correct |
52 ms |
111428 KB |
Output is correct |
7 |
Correct |
53 ms |
111472 KB |
Output is correct |
8 |
Correct |
62 ms |
111492 KB |
Output is correct |
9 |
Correct |
56 ms |
111472 KB |
Output is correct |
10 |
Correct |
78 ms |
111736 KB |
Output is correct |
11 |
Correct |
187 ms |
112840 KB |
Output is correct |
12 |
Correct |
76 ms |
111816 KB |
Output is correct |
13 |
Correct |
58 ms |
111764 KB |
Output is correct |
14 |
Correct |
73 ms |
111996 KB |
Output is correct |
15 |
Correct |
129 ms |
112108 KB |
Output is correct |
16 |
Correct |
281 ms |
113224 KB |
Output is correct |
17 |
Correct |
242 ms |
119296 KB |
Output is correct |
18 |
Correct |
276 ms |
119264 KB |
Output is correct |
19 |
Correct |
245 ms |
119396 KB |
Output is correct |
20 |
Correct |
284 ms |
119696 KB |
Output is correct |
21 |
Correct |
559 ms |
120956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
111524 KB |
Output is correct |
2 |
Correct |
79 ms |
111620 KB |
Output is correct |
3 |
Correct |
148 ms |
112264 KB |
Output is correct |
4 |
Correct |
239 ms |
112936 KB |
Output is correct |
5 |
Correct |
87 ms |
112192 KB |
Output is correct |
6 |
Correct |
103 ms |
112400 KB |
Output is correct |
7 |
Correct |
225 ms |
113056 KB |
Output is correct |
8 |
Correct |
371 ms |
113884 KB |
Output is correct |
9 |
Correct |
156 ms |
115592 KB |
Output is correct |
10 |
Correct |
258 ms |
115704 KB |
Output is correct |
11 |
Correct |
341 ms |
116396 KB |
Output is correct |
12 |
Correct |
516 ms |
117192 KB |
Output is correct |
13 |
Correct |
302 ms |
119732 KB |
Output is correct |
14 |
Correct |
370 ms |
119948 KB |
Output is correct |
15 |
Correct |
562 ms |
120452 KB |
Output is correct |
16 |
Correct |
653 ms |
121452 KB |
Output is correct |
17 |
Correct |
668 ms |
121128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
779 ms |
123536 KB |
Output is correct |
2 |
Correct |
789 ms |
123508 KB |
Output is correct |
3 |
Correct |
727 ms |
123588 KB |
Output is correct |
4 |
Correct |
731 ms |
123560 KB |
Output is correct |
5 |
Correct |
713 ms |
123664 KB |
Output is correct |
6 |
Correct |
653 ms |
123696 KB |
Output is correct |
7 |
Correct |
868 ms |
125796 KB |
Output is correct |
8 |
Correct |
908 ms |
125844 KB |
Output is correct |
9 |
Correct |
873 ms |
125820 KB |
Output is correct |
10 |
Correct |
891 ms |
125796 KB |
Output is correct |
11 |
Correct |
958 ms |
125708 KB |
Output is correct |
12 |
Correct |
831 ms |
125336 KB |
Output is correct |
13 |
Correct |
1111 ms |
129120 KB |
Output is correct |
14 |
Correct |
1075 ms |
129204 KB |
Output is correct |
15 |
Correct |
1115 ms |
129228 KB |
Output is correct |
16 |
Correct |
1012 ms |
129312 KB |
Output is correct |
17 |
Correct |
1057 ms |
128688 KB |
Output is correct |
18 |
Correct |
852 ms |
126552 KB |
Output is correct |
19 |
Correct |
1059 ms |
129080 KB |
Output is correct |
20 |
Correct |
1054 ms |
129080 KB |
Output is correct |
21 |
Correct |
1051 ms |
129180 KB |
Output is correct |
22 |
Correct |
1069 ms |
129228 KB |
Output is correct |
23 |
Correct |
1042 ms |
128720 KB |
Output is correct |
24 |
Correct |
868 ms |
126660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
111420 KB |
Output is correct |
2 |
Correct |
60 ms |
111504 KB |
Output is correct |
3 |
Correct |
54 ms |
111416 KB |
Output is correct |
4 |
Correct |
50 ms |
111456 KB |
Output is correct |
5 |
Correct |
50 ms |
111388 KB |
Output is correct |
6 |
Correct |
54 ms |
111436 KB |
Output is correct |
7 |
Correct |
63 ms |
111440 KB |
Output is correct |
8 |
Correct |
71 ms |
111380 KB |
Output is correct |
9 |
Correct |
67 ms |
111420 KB |
Output is correct |
10 |
Correct |
53 ms |
111396 KB |
Output is correct |
11 |
Correct |
51 ms |
111440 KB |
Output is correct |
12 |
Correct |
54 ms |
111416 KB |
Output is correct |
13 |
Correct |
82 ms |
111392 KB |
Output is correct |
14 |
Correct |
57 ms |
111420 KB |
Output is correct |
15 |
Correct |
53 ms |
111380 KB |
Output is correct |
16 |
Correct |
73 ms |
111372 KB |
Output is correct |
17 |
Correct |
50 ms |
111564 KB |
Output is correct |
18 |
Correct |
47 ms |
111432 KB |
Output is correct |
19 |
Correct |
68 ms |
111596 KB |
Output is correct |
20 |
Correct |
82 ms |
111580 KB |
Output is correct |
21 |
Correct |
75 ms |
111588 KB |
Output is correct |
22 |
Correct |
69 ms |
111604 KB |
Output is correct |
23 |
Correct |
114 ms |
111868 KB |
Output is correct |
24 |
Correct |
94 ms |
111944 KB |
Output is correct |
25 |
Correct |
77 ms |
111908 KB |
Output is correct |
26 |
Correct |
79 ms |
112240 KB |
Output is correct |
27 |
Correct |
50 ms |
111476 KB |
Output is correct |
28 |
Correct |
55 ms |
111472 KB |
Output is correct |
29 |
Correct |
72 ms |
111504 KB |
Output is correct |
30 |
Correct |
87 ms |
111624 KB |
Output is correct |
31 |
Correct |
155 ms |
112652 KB |
Output is correct |
32 |
Correct |
52 ms |
111428 KB |
Output is correct |
33 |
Correct |
53 ms |
111472 KB |
Output is correct |
34 |
Correct |
62 ms |
111492 KB |
Output is correct |
35 |
Correct |
56 ms |
111472 KB |
Output is correct |
36 |
Correct |
78 ms |
111736 KB |
Output is correct |
37 |
Correct |
187 ms |
112840 KB |
Output is correct |
38 |
Correct |
76 ms |
111816 KB |
Output is correct |
39 |
Correct |
58 ms |
111764 KB |
Output is correct |
40 |
Correct |
73 ms |
111996 KB |
Output is correct |
41 |
Correct |
129 ms |
112108 KB |
Output is correct |
42 |
Correct |
281 ms |
113224 KB |
Output is correct |
43 |
Correct |
242 ms |
119296 KB |
Output is correct |
44 |
Correct |
276 ms |
119264 KB |
Output is correct |
45 |
Correct |
245 ms |
119396 KB |
Output is correct |
46 |
Correct |
284 ms |
119696 KB |
Output is correct |
47 |
Correct |
559 ms |
120956 KB |
Output is correct |
48 |
Correct |
90 ms |
111524 KB |
Output is correct |
49 |
Correct |
79 ms |
111620 KB |
Output is correct |
50 |
Correct |
148 ms |
112264 KB |
Output is correct |
51 |
Correct |
239 ms |
112936 KB |
Output is correct |
52 |
Correct |
87 ms |
112192 KB |
Output is correct |
53 |
Correct |
103 ms |
112400 KB |
Output is correct |
54 |
Correct |
225 ms |
113056 KB |
Output is correct |
55 |
Correct |
371 ms |
113884 KB |
Output is correct |
56 |
Correct |
156 ms |
115592 KB |
Output is correct |
57 |
Correct |
258 ms |
115704 KB |
Output is correct |
58 |
Correct |
341 ms |
116396 KB |
Output is correct |
59 |
Correct |
516 ms |
117192 KB |
Output is correct |
60 |
Correct |
302 ms |
119732 KB |
Output is correct |
61 |
Correct |
370 ms |
119948 KB |
Output is correct |
62 |
Correct |
562 ms |
120452 KB |
Output is correct |
63 |
Correct |
653 ms |
121452 KB |
Output is correct |
64 |
Correct |
668 ms |
121128 KB |
Output is correct |
65 |
Correct |
779 ms |
123536 KB |
Output is correct |
66 |
Correct |
789 ms |
123508 KB |
Output is correct |
67 |
Correct |
727 ms |
123588 KB |
Output is correct |
68 |
Correct |
731 ms |
123560 KB |
Output is correct |
69 |
Correct |
713 ms |
123664 KB |
Output is correct |
70 |
Correct |
653 ms |
123696 KB |
Output is correct |
71 |
Correct |
868 ms |
125796 KB |
Output is correct |
72 |
Correct |
908 ms |
125844 KB |
Output is correct |
73 |
Correct |
873 ms |
125820 KB |
Output is correct |
74 |
Correct |
891 ms |
125796 KB |
Output is correct |
75 |
Correct |
958 ms |
125708 KB |
Output is correct |
76 |
Correct |
831 ms |
125336 KB |
Output is correct |
77 |
Correct |
1111 ms |
129120 KB |
Output is correct |
78 |
Correct |
1075 ms |
129204 KB |
Output is correct |
79 |
Correct |
1115 ms |
129228 KB |
Output is correct |
80 |
Correct |
1012 ms |
129312 KB |
Output is correct |
81 |
Correct |
1057 ms |
128688 KB |
Output is correct |
82 |
Correct |
852 ms |
126552 KB |
Output is correct |
83 |
Correct |
1059 ms |
129080 KB |
Output is correct |
84 |
Correct |
1054 ms |
129080 KB |
Output is correct |
85 |
Correct |
1051 ms |
129180 KB |
Output is correct |
86 |
Correct |
1069 ms |
129228 KB |
Output is correct |
87 |
Correct |
1042 ms |
128720 KB |
Output is correct |
88 |
Correct |
868 ms |
126660 KB |
Output is correct |
89 |
Correct |
659 ms |
122700 KB |
Output is correct |
90 |
Correct |
631 ms |
122952 KB |
Output is correct |
91 |
Correct |
714 ms |
124200 KB |
Output is correct |
92 |
Correct |
721 ms |
124096 KB |
Output is correct |
93 |
Correct |
821 ms |
126228 KB |
Output is correct |
94 |
Correct |
841 ms |
125216 KB |
Output is correct |
95 |
Correct |
1020 ms |
126544 KB |
Output is correct |
96 |
Correct |
928 ms |
125780 KB |
Output is correct |
97 |
Correct |
958 ms |
126568 KB |
Output is correct |
98 |
Correct |
978 ms |
128516 KB |
Output is correct |
99 |
Correct |
936 ms |
126256 KB |
Output is correct |
100 |
Correct |
937 ms |
126264 KB |
Output is correct |