#include <bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = (int)1e5 + 2;
const ll inf = 1ll << 60;
typedef pair<int, int> pii;
int lg[N];
struct TTree { /// get max value in range, add x in a range
vector<pair<ll, int>> st;
vector<ll> lz;
vector<pii> range;
int n, h; ll val;
pair<ll, int> top;
void init(int _n) {
n = _n; h = sizeof(int) * 8 - __builtin_clz(n);
st.resize(2 * n + 2, mp(0, 0));
lz.resize(2 * n + 2, 0);
for(int i = n - 1; i >= 0; --i) st[i + n].se = i;
}
void apply(int x, ll val) {
st[x].fi += val;
if(x < n) lz[x] += val;
}
inline pair<ll, int> Max(const pair<ll, int>& x, const pair<ll, int>& y) {
if(x.fi < y.fi) return y;
return x;
}
void build(int x) {
while(x > 1) {
x >>= 1;
st[x] = Max(st[x << 1], st[x << 1 | 1]);
st[x].fi += lz[x];
}
}
void push(int x) {
for(int i, s = h; s > 0; --s) {
i = x >> s;
if(lz[i] != 0) {
apply(x << 1, lz[i]);
apply(x << 1 | 1, lz[i]);
lz[i] = 0;
}
}
}
void upd(int l, int r, ll val) {
l += n, r += (n + 1);
int l0 = l, r0 = r;
for(; l < r; l >>= 1, r >>= 1) {
if(l & 1) apply(l ++, val);
if(r & 1) apply(-- r, val);
}
build(l0); build(r0 - 1);
}
ll diameter() {
top = st[1]; val = st[1].fi;
upd(range[top.se].fi, range[top.se].se, -top.fi);
val += max(st[1].fi, 0ll);
upd(range[top.se].fi, range[top.se].se, top.fi);
return val;
}
};
vector<TTree> it;
struct TEdge {
int u, v; ll w;
vector<int> it;
vector<pii> range;
} e[N];
vector<pii> adj[N];
ll W, dis[N];
int n, q, Time, head[N], in[N], out[N], sz[N], big[N];
bool del[N];
int find(int u) {
function<void(int, int)> dfs = [&](int u, int p) {
sz[u] = 1, big[u] = 0;
for(auto v: adj[u]) {
if(v.fi == p || del[v.fi]) continue;
dfs(v.fi, u);
sz[u] += sz[v.fi];
if(sz[v.fi] > sz[big[u]]) big[u] = v.fi;
}
};
dfs(u, -1);
int cen = u;
while(sz[big[cen]] * 2 >= sz[u] && big[cen]) cen = big[cen];
return cen;
}
multiset<ll, greater<ll>> ans;
void centroid(int u) {
int root = find(u);
it.push_back({});
function<void(int, int)> dfs = [&](int u, int p) {
in[u] = ++Time;
if(p == root) head[u] = u;
else if(p != -1) head[u] = head[p];
for(auto v: adj[u]) {
if(del[v.fi] || v.fi == p) continue;
dis[v.fi] = dis[u] + e[v.se].w;
it.back().range.pb(v.se, v.fi);
dfs(v.fi, u);
}
out[u] = Time;
};
Time = -2, dis[root] = 0;
dfs(root, -1); del[root] = 1;
if((int)it.back().range.size()) {
it.back().init((int)it.back().range.size());
for(auto& p: it.back().range) {
e[p.fi].it.pb((int)it.size() - 1);
e[p.fi].range.pb(in[p.se], out[p.se]);
it.back().upd(in[p.se], in[p.se], dis[p.se]);
p.fi = in[head[p.se]], p.se = out[head[p.se]];
}
ans.insert(it.back().diameter());
}
for(auto v: adj[root]) {
if(del[v.fi]) continue;
centroid(v.fi);
}
}
///40071305542068
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define Task "test"
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> q >> W;
for(int i = 1; i <= n; ++i) lg[i] = log2(i) + 1;
for(int i = 0; i < n - 1; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
adj[e[i].u].pb(e[i].v, i);
adj[e[i].v].pb(e[i].u, i);
}
centroid(1); ll w, lst = 0;
for(int id, tree; q > 0; --q) {
cin >> id >> w;
id = ((ll)id + lst) % (n - 1);
w = (w + lst) % W;
for(int i = 0; i < e[id].it.size(); ++i) {
tree = e[id].it[i];
ans.erase(ans.find(it[tree].diameter()));
it[tree].upd((int)e[id].range[i].fi, (int)e[id].range[i].se, w - e[id].w);
ans.insert(it[tree].diameter());
}
e[id].w = w;
cout << (lst = *ans.begin()) << '\n';
}
}
Compilation message
diameter.cpp: In function 'int32_t main()':
diameter.cpp:154:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < e[id].it.size(); ++i) {
~~^~~~~~~~~~~~~~~~~
diameter.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void centroid(int)':
diameter.cpp:104:29: warning: array subscript is below array bounds [-Warray-bounds]
if(p == root) head[u] = u;
~~~~~~^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
10 ms |
8960 KB |
Output is correct |
6 |
Correct |
10 ms |
8960 KB |
Output is correct |
7 |
Correct |
10 ms |
8960 KB |
Output is correct |
8 |
Correct |
11 ms |
8992 KB |
Output is correct |
9 |
Correct |
11 ms |
9088 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
10 ms |
8960 KB |
Output is correct |
12 |
Correct |
10 ms |
8960 KB |
Output is correct |
13 |
Correct |
10 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
10 ms |
8960 KB |
Output is correct |
6 |
Correct |
10 ms |
8960 KB |
Output is correct |
7 |
Correct |
10 ms |
8960 KB |
Output is correct |
8 |
Correct |
11 ms |
8992 KB |
Output is correct |
9 |
Correct |
11 ms |
9088 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
10 ms |
8960 KB |
Output is correct |
12 |
Correct |
10 ms |
8960 KB |
Output is correct |
13 |
Correct |
10 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
19 |
Correct |
37 ms |
9728 KB |
Output is correct |
20 |
Correct |
36 ms |
9728 KB |
Output is correct |
21 |
Correct |
42 ms |
9876 KB |
Output is correct |
22 |
Correct |
40 ms |
9984 KB |
Output is correct |
23 |
Correct |
59 ms |
12588 KB |
Output is correct |
24 |
Correct |
77 ms |
13444 KB |
Output is correct |
25 |
Correct |
77 ms |
13960 KB |
Output is correct |
26 |
Correct |
95 ms |
15104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9088 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
11 ms |
8960 KB |
Output is correct |
4 |
Correct |
22 ms |
9216 KB |
Output is correct |
5 |
Correct |
74 ms |
9592 KB |
Output is correct |
6 |
Correct |
10 ms |
8960 KB |
Output is correct |
7 |
Correct |
11 ms |
9216 KB |
Output is correct |
8 |
Correct |
11 ms |
9216 KB |
Output is correct |
9 |
Correct |
13 ms |
9216 KB |
Output is correct |
10 |
Correct |
33 ms |
9344 KB |
Output is correct |
11 |
Correct |
110 ms |
9792 KB |
Output is correct |
12 |
Correct |
14 ms |
10972 KB |
Output is correct |
13 |
Correct |
15 ms |
10972 KB |
Output is correct |
14 |
Correct |
18 ms |
10972 KB |
Output is correct |
15 |
Correct |
42 ms |
11100 KB |
Output is correct |
16 |
Correct |
148 ms |
11200 KB |
Output is correct |
17 |
Correct |
97 ms |
42136 KB |
Output is correct |
18 |
Correct |
105 ms |
42184 KB |
Output is correct |
19 |
Correct |
101 ms |
42156 KB |
Output is correct |
20 |
Correct |
133 ms |
42136 KB |
Output is correct |
21 |
Correct |
236 ms |
42148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
9856 KB |
Output is correct |
2 |
Correct |
58 ms |
9984 KB |
Output is correct |
3 |
Correct |
213 ms |
10104 KB |
Output is correct |
4 |
Correct |
402 ms |
10644 KB |
Output is correct |
5 |
Correct |
50 ms |
19396 KB |
Output is correct |
6 |
Correct |
120 ms |
19516 KB |
Output is correct |
7 |
Correct |
452 ms |
19748 KB |
Output is correct |
8 |
Correct |
786 ms |
20052 KB |
Output is correct |
9 |
Correct |
241 ms |
67324 KB |
Output is correct |
10 |
Correct |
371 ms |
67452 KB |
Output is correct |
11 |
Correct |
859 ms |
67708 KB |
Output is correct |
12 |
Correct |
1617 ms |
68348 KB |
Output is correct |
13 |
Correct |
465 ms |
131208 KB |
Output is correct |
14 |
Correct |
638 ms |
131316 KB |
Output is correct |
15 |
Correct |
1358 ms |
131632 KB |
Output is correct |
16 |
Correct |
2080 ms |
131856 KB |
Output is correct |
17 |
Correct |
3783 ms |
132044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2856 ms |
110444 KB |
Output is correct |
2 |
Correct |
3099 ms |
113240 KB |
Output is correct |
3 |
Correct |
2806 ms |
112300 KB |
Output is correct |
4 |
Correct |
3064 ms |
112952 KB |
Output is correct |
5 |
Correct |
3030 ms |
107276 KB |
Output is correct |
6 |
Correct |
2661 ms |
80388 KB |
Output is correct |
7 |
Correct |
4336 ms |
136712 KB |
Output is correct |
8 |
Correct |
3789 ms |
140376 KB |
Output is correct |
9 |
Correct |
3902 ms |
140512 KB |
Output is correct |
10 |
Correct |
4056 ms |
140084 KB |
Output is correct |
11 |
Correct |
3813 ms |
132988 KB |
Output is correct |
12 |
Correct |
3250 ms |
98296 KB |
Output is correct |
13 |
Correct |
4159 ms |
155024 KB |
Output is correct |
14 |
Correct |
4233 ms |
155112 KB |
Output is correct |
15 |
Correct |
4260 ms |
155396 KB |
Output is correct |
16 |
Correct |
4144 ms |
154612 KB |
Output is correct |
17 |
Correct |
4014 ms |
146052 KB |
Output is correct |
18 |
Correct |
3270 ms |
103708 KB |
Output is correct |
19 |
Correct |
4365 ms |
155156 KB |
Output is correct |
20 |
Correct |
4080 ms |
155332 KB |
Output is correct |
21 |
Correct |
4272 ms |
155076 KB |
Output is correct |
22 |
Correct |
4264 ms |
154436 KB |
Output is correct |
23 |
Correct |
4552 ms |
145564 KB |
Output is correct |
24 |
Correct |
3717 ms |
103068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
10 ms |
8960 KB |
Output is correct |
6 |
Correct |
10 ms |
8960 KB |
Output is correct |
7 |
Correct |
10 ms |
8960 KB |
Output is correct |
8 |
Correct |
11 ms |
8992 KB |
Output is correct |
9 |
Correct |
11 ms |
9088 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
10 ms |
8960 KB |
Output is correct |
12 |
Correct |
10 ms |
8960 KB |
Output is correct |
13 |
Correct |
10 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
19 |
Correct |
37 ms |
9728 KB |
Output is correct |
20 |
Correct |
36 ms |
9728 KB |
Output is correct |
21 |
Correct |
42 ms |
9876 KB |
Output is correct |
22 |
Correct |
40 ms |
9984 KB |
Output is correct |
23 |
Correct |
59 ms |
12588 KB |
Output is correct |
24 |
Correct |
77 ms |
13444 KB |
Output is correct |
25 |
Correct |
77 ms |
13960 KB |
Output is correct |
26 |
Correct |
95 ms |
15104 KB |
Output is correct |
27 |
Correct |
10 ms |
9088 KB |
Output is correct |
28 |
Correct |
10 ms |
8960 KB |
Output is correct |
29 |
Correct |
11 ms |
8960 KB |
Output is correct |
30 |
Correct |
22 ms |
9216 KB |
Output is correct |
31 |
Correct |
74 ms |
9592 KB |
Output is correct |
32 |
Correct |
10 ms |
8960 KB |
Output is correct |
33 |
Correct |
11 ms |
9216 KB |
Output is correct |
34 |
Correct |
11 ms |
9216 KB |
Output is correct |
35 |
Correct |
13 ms |
9216 KB |
Output is correct |
36 |
Correct |
33 ms |
9344 KB |
Output is correct |
37 |
Correct |
110 ms |
9792 KB |
Output is correct |
38 |
Correct |
14 ms |
10972 KB |
Output is correct |
39 |
Correct |
15 ms |
10972 KB |
Output is correct |
40 |
Correct |
18 ms |
10972 KB |
Output is correct |
41 |
Correct |
42 ms |
11100 KB |
Output is correct |
42 |
Correct |
148 ms |
11200 KB |
Output is correct |
43 |
Correct |
97 ms |
42136 KB |
Output is correct |
44 |
Correct |
105 ms |
42184 KB |
Output is correct |
45 |
Correct |
101 ms |
42156 KB |
Output is correct |
46 |
Correct |
133 ms |
42136 KB |
Output is correct |
47 |
Correct |
236 ms |
42148 KB |
Output is correct |
48 |
Correct |
16 ms |
9856 KB |
Output is correct |
49 |
Correct |
58 ms |
9984 KB |
Output is correct |
50 |
Correct |
213 ms |
10104 KB |
Output is correct |
51 |
Correct |
402 ms |
10644 KB |
Output is correct |
52 |
Correct |
50 ms |
19396 KB |
Output is correct |
53 |
Correct |
120 ms |
19516 KB |
Output is correct |
54 |
Correct |
452 ms |
19748 KB |
Output is correct |
55 |
Correct |
786 ms |
20052 KB |
Output is correct |
56 |
Correct |
241 ms |
67324 KB |
Output is correct |
57 |
Correct |
371 ms |
67452 KB |
Output is correct |
58 |
Correct |
859 ms |
67708 KB |
Output is correct |
59 |
Correct |
1617 ms |
68348 KB |
Output is correct |
60 |
Correct |
465 ms |
131208 KB |
Output is correct |
61 |
Correct |
638 ms |
131316 KB |
Output is correct |
62 |
Correct |
1358 ms |
131632 KB |
Output is correct |
63 |
Correct |
2080 ms |
131856 KB |
Output is correct |
64 |
Correct |
3783 ms |
132044 KB |
Output is correct |
65 |
Correct |
2856 ms |
110444 KB |
Output is correct |
66 |
Correct |
3099 ms |
113240 KB |
Output is correct |
67 |
Correct |
2806 ms |
112300 KB |
Output is correct |
68 |
Correct |
3064 ms |
112952 KB |
Output is correct |
69 |
Correct |
3030 ms |
107276 KB |
Output is correct |
70 |
Correct |
2661 ms |
80388 KB |
Output is correct |
71 |
Correct |
4336 ms |
136712 KB |
Output is correct |
72 |
Correct |
3789 ms |
140376 KB |
Output is correct |
73 |
Correct |
3902 ms |
140512 KB |
Output is correct |
74 |
Correct |
4056 ms |
140084 KB |
Output is correct |
75 |
Correct |
3813 ms |
132988 KB |
Output is correct |
76 |
Correct |
3250 ms |
98296 KB |
Output is correct |
77 |
Correct |
4159 ms |
155024 KB |
Output is correct |
78 |
Correct |
4233 ms |
155112 KB |
Output is correct |
79 |
Correct |
4260 ms |
155396 KB |
Output is correct |
80 |
Correct |
4144 ms |
154612 KB |
Output is correct |
81 |
Correct |
4014 ms |
146052 KB |
Output is correct |
82 |
Correct |
3270 ms |
103708 KB |
Output is correct |
83 |
Correct |
4365 ms |
155156 KB |
Output is correct |
84 |
Correct |
4080 ms |
155332 KB |
Output is correct |
85 |
Correct |
4272 ms |
155076 KB |
Output is correct |
86 |
Correct |
4264 ms |
154436 KB |
Output is correct |
87 |
Correct |
4552 ms |
145564 KB |
Output is correct |
88 |
Correct |
3717 ms |
103068 KB |
Output is correct |
89 |
Correct |
2945 ms |
114580 KB |
Output is correct |
90 |
Correct |
3713 ms |
123928 KB |
Output is correct |
91 |
Correct |
4339 ms |
135696 KB |
Output is correct |
92 |
Correct |
4311 ms |
139108 KB |
Output is correct |
93 |
Correct |
4303 ms |
144748 KB |
Output is correct |
94 |
Correct |
4433 ms |
146736 KB |
Output is correct |
95 |
Correct |
4129 ms |
151432 KB |
Output is correct |
96 |
Correct |
4528 ms |
150492 KB |
Output is correct |
97 |
Correct |
4447 ms |
151648 KB |
Output is correct |
98 |
Correct |
4139 ms |
154036 KB |
Output is correct |
99 |
Correct |
4272 ms |
150972 KB |
Output is correct |
100 |
Correct |
4446 ms |
151304 KB |
Output is correct |