#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast")
using namespace std;
struct edge {
int u, v;
long long w;
int other( int x ) {
return u ^ v ^ x;
}
};
const int MAX_N = 1e5;
edge edges[MAX_N];
vector<int> adj[MAX_N + 1];
struct SegTree {
int ll, rr;
vector<long long> segTree, lazy;
void propag( int v, int l, int r ) {
segTree[v] += lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] += lazy[v];
lazy[v * 2 + 2] += lazy[v];
}
lazy[v] = 0;
}
void init( int l, int r ) {
ll = l;
rr = r;
segTree.resize( 4 * (r - l + 1) );
lazy.resize( 4 * (r - l + 1) );
}
void update( int v, int l, int r, int lu, int ru, long long x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
}
void update( int l, int r, long long x ) {
update( 0, ll, rr, l, r, x );
}
long long query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return 0;
if ( segTree[v] == 0 )
return 0;
if ( lq <= l && r <= rq )
return segTree[v];
int mid = (l + r) / 2;
return max( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
}
long long queryAll() {
return segTree[0];
}
};
SegTree depths[2 * MAX_N + 1];
bool isCentroid[MAX_N + 1];
int sz[MAX_N + 1];
void calcSizes( int u, int p ) {
sz[u] = 1;
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
calcSizes( v, u );
sz[u] += sz[v];
}
}
int totSz;
int findCentroid( int u, int p ) {
int c = 0, maxSz = totSz - sz[u];
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
int d = findCentroid( v, u );
if ( d != 0 )
c = d;
maxSz = max( maxSz, sz[v] );
}
if ( maxSz <= totSz / 2 )
c = u;
return c;
}
struct info {
int c, h, l, r;
};
vector<info> centroids[MAX_N];
vector<int> heads[MAX_N + 1];
int crtPos, headId;
void dfs( int u, int p, int c, int h ) {
int children = 0;
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
info x;
x.c = c;
x.h = headId;
x.l = crtPos;
dfs( v, u, c, h );
x.r = crtPos - 1;
children++;
centroids[e].push_back( x );
}
if ( children == 0 )
crtPos++;
}
void decomp( int r ) {
calcSizes( r, 0 );
totSz = sz[r];
int c = findCentroid( r, 0 );
for ( int e: adj[c] ) {
int v = edges[e].other( c );
if ( isCentroid[v] )
continue;
heads[c].push_back( headId );
crtPos = 0;
dfs( v, c, c, e );
centroids[e].push_back( { c, headId, 0, crtPos - 1 } );
depths[headId].init( 0, crtPos - 1 );
headId++;
}
isCentroid[c] = true;
for ( int e: adj[c] ) {
int v = edges[e].other( c );
if ( isCentroid[v] )
continue;
decomp( v );
}
}
multiset<long long> diameterByCentroid[MAX_N + 1], allDiameters;
signed main() {
int n, q;
long long m;
cin >> n >> q >> m;
for ( int e = 0; e < n - 1; e++ ) {
cin >> edges[e].u >> edges[e].v >> edges[e].w;
adj[edges[e].u].push_back( e );
adj[edges[e].v].push_back( e );
}
decomp( 1 );
for ( int e = 0; e < n - 1; e++ ) {
int w = edges[e].w;
for ( auto x: centroids[e] ) {
int c = x.c, h = x.h, l = x.l, r = x.r;
depths[h].update( l, r, w );
}
}
for ( int c = 1; c <= n; c++ ) {
for ( int h: heads[c] )
diameterByCentroid[c].insert( depths[h].queryAll() );
long long d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
long long d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
allDiameters.insert( d1 + d2 );
}
long long last = 0;
while ( q-- ) {
int e;
long long w;
cin >> e >> w;
e = (e + last) % (n - 1);
w = (w + last) % m;
for ( auto x: centroids[e] ) {
long long d1, d2, maxDepth;
int c = x.c, h = x.h, l = x.l, r = x.r;
d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
allDiameters.erase( allDiameters.lower_bound( d1 + d2 ) );
maxDepth = depths[h].queryAll();
diameterByCentroid[c].erase( diameterByCentroid[c].lower_bound( maxDepth ) );
depths[h].update( l, r, w - edges[e].w );
maxDepth = depths[h].queryAll();
diameterByCentroid[c].insert( maxDepth );
d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
allDiameters.insert( d1 + d2 );
}
edges[e].w = w;
last = *allDiameters.rbegin();
cout << last << "\n";
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:194:17: warning: unused variable 'c' [-Wunused-variable]
194 | int c = x.c, h = x.h, l = x.l, r = x.r;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27224 KB |
Output is correct |
2 |
Correct |
5 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27228 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
5 ms |
27224 KB |
Output is correct |
7 |
Correct |
6 ms |
27228 KB |
Output is correct |
8 |
Correct |
7 ms |
27480 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
11 |
Correct |
6 ms |
27228 KB |
Output is correct |
12 |
Correct |
6 ms |
27092 KB |
Output is correct |
13 |
Correct |
6 ms |
27224 KB |
Output is correct |
14 |
Correct |
6 ms |
27320 KB |
Output is correct |
15 |
Correct |
6 ms |
27228 KB |
Output is correct |
16 |
Correct |
6 ms |
27228 KB |
Output is correct |
17 |
Correct |
7 ms |
27228 KB |
Output is correct |
18 |
Correct |
7 ms |
27228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27224 KB |
Output is correct |
2 |
Correct |
5 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27228 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
5 ms |
27224 KB |
Output is correct |
7 |
Correct |
6 ms |
27228 KB |
Output is correct |
8 |
Correct |
7 ms |
27480 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
11 |
Correct |
6 ms |
27228 KB |
Output is correct |
12 |
Correct |
6 ms |
27092 KB |
Output is correct |
13 |
Correct |
6 ms |
27224 KB |
Output is correct |
14 |
Correct |
6 ms |
27320 KB |
Output is correct |
15 |
Correct |
6 ms |
27228 KB |
Output is correct |
16 |
Correct |
6 ms |
27228 KB |
Output is correct |
17 |
Correct |
7 ms |
27228 KB |
Output is correct |
18 |
Correct |
7 ms |
27228 KB |
Output is correct |
19 |
Correct |
30 ms |
27740 KB |
Output is correct |
20 |
Correct |
23 ms |
27740 KB |
Output is correct |
21 |
Correct |
25 ms |
27740 KB |
Output is correct |
22 |
Correct |
30 ms |
27996 KB |
Output is correct |
23 |
Correct |
44 ms |
30436 KB |
Output is correct |
24 |
Correct |
42 ms |
31064 KB |
Output is correct |
25 |
Correct |
48 ms |
31572 KB |
Output is correct |
26 |
Correct |
39 ms |
31320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
27228 KB |
Output is correct |
2 |
Correct |
6 ms |
27228 KB |
Output is correct |
3 |
Correct |
9 ms |
27224 KB |
Output is correct |
4 |
Correct |
40 ms |
27484 KB |
Output is correct |
5 |
Correct |
173 ms |
27616 KB |
Output is correct |
6 |
Correct |
6 ms |
27224 KB |
Output is correct |
7 |
Correct |
7 ms |
27228 KB |
Output is correct |
8 |
Correct |
6 ms |
27228 KB |
Output is correct |
9 |
Correct |
10 ms |
27224 KB |
Output is correct |
10 |
Correct |
41 ms |
27472 KB |
Output is correct |
11 |
Correct |
180 ms |
27732 KB |
Output is correct |
12 |
Correct |
10 ms |
28504 KB |
Output is correct |
13 |
Correct |
11 ms |
28508 KB |
Output is correct |
14 |
Correct |
14 ms |
28508 KB |
Output is correct |
15 |
Correct |
52 ms |
28752 KB |
Output is correct |
16 |
Correct |
208 ms |
29044 KB |
Output is correct |
17 |
Correct |
118 ms |
56008 KB |
Output is correct |
18 |
Correct |
119 ms |
56004 KB |
Output is correct |
19 |
Correct |
155 ms |
56004 KB |
Output is correct |
20 |
Correct |
171 ms |
56008 KB |
Output is correct |
21 |
Correct |
434 ms |
56516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
27740 KB |
Output is correct |
2 |
Correct |
34 ms |
27992 KB |
Output is correct |
3 |
Correct |
141 ms |
28076 KB |
Output is correct |
4 |
Correct |
276 ms |
28496 KB |
Output is correct |
5 |
Correct |
36 ms |
37460 KB |
Output is correct |
6 |
Correct |
69 ms |
37512 KB |
Output is correct |
7 |
Correct |
209 ms |
37716 KB |
Output is correct |
8 |
Correct |
395 ms |
37980 KB |
Output is correct |
9 |
Correct |
178 ms |
83544 KB |
Output is correct |
10 |
Correct |
219 ms |
83536 KB |
Output is correct |
11 |
Correct |
419 ms |
83860 KB |
Output is correct |
12 |
Correct |
660 ms |
84120 KB |
Output is correct |
13 |
Correct |
382 ms |
143916 KB |
Output is correct |
14 |
Correct |
433 ms |
143892 KB |
Output is correct |
15 |
Correct |
678 ms |
144444 KB |
Output is correct |
16 |
Correct |
1087 ms |
144928 KB |
Output is correct |
17 |
Correct |
1881 ms |
144592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1743 ms |
123116 KB |
Output is correct |
2 |
Correct |
1854 ms |
129056 KB |
Output is correct |
3 |
Correct |
1734 ms |
128684 KB |
Output is correct |
4 |
Correct |
1847 ms |
128812 KB |
Output is correct |
5 |
Correct |
1729 ms |
125196 KB |
Output is correct |
6 |
Correct |
1388 ms |
96404 KB |
Output is correct |
7 |
Correct |
2256 ms |
137840 KB |
Output is correct |
8 |
Correct |
2333 ms |
137748 KB |
Output is correct |
9 |
Correct |
2306 ms |
137624 KB |
Output is correct |
10 |
Correct |
2206 ms |
137356 KB |
Output is correct |
11 |
Correct |
2086 ms |
132584 KB |
Output is correct |
12 |
Correct |
1656 ms |
100216 KB |
Output is correct |
13 |
Correct |
1614 ms |
118800 KB |
Output is correct |
14 |
Correct |
1537 ms |
119440 KB |
Output is correct |
15 |
Correct |
1801 ms |
119188 KB |
Output is correct |
16 |
Correct |
1854 ms |
119012 KB |
Output is correct |
17 |
Correct |
1712 ms |
115960 KB |
Output is correct |
18 |
Correct |
1401 ms |
92648 KB |
Output is correct |
19 |
Correct |
1699 ms |
118648 KB |
Output is correct |
20 |
Correct |
1726 ms |
118556 KB |
Output is correct |
21 |
Correct |
1646 ms |
118904 KB |
Output is correct |
22 |
Correct |
1818 ms |
118644 KB |
Output is correct |
23 |
Correct |
1673 ms |
116064 KB |
Output is correct |
24 |
Correct |
1343 ms |
92680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27224 KB |
Output is correct |
2 |
Correct |
5 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27228 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
5 ms |
27224 KB |
Output is correct |
7 |
Correct |
6 ms |
27228 KB |
Output is correct |
8 |
Correct |
7 ms |
27480 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
11 |
Correct |
6 ms |
27228 KB |
Output is correct |
12 |
Correct |
6 ms |
27092 KB |
Output is correct |
13 |
Correct |
6 ms |
27224 KB |
Output is correct |
14 |
Correct |
6 ms |
27320 KB |
Output is correct |
15 |
Correct |
6 ms |
27228 KB |
Output is correct |
16 |
Correct |
6 ms |
27228 KB |
Output is correct |
17 |
Correct |
7 ms |
27228 KB |
Output is correct |
18 |
Correct |
7 ms |
27228 KB |
Output is correct |
19 |
Correct |
30 ms |
27740 KB |
Output is correct |
20 |
Correct |
23 ms |
27740 KB |
Output is correct |
21 |
Correct |
25 ms |
27740 KB |
Output is correct |
22 |
Correct |
30 ms |
27996 KB |
Output is correct |
23 |
Correct |
44 ms |
30436 KB |
Output is correct |
24 |
Correct |
42 ms |
31064 KB |
Output is correct |
25 |
Correct |
48 ms |
31572 KB |
Output is correct |
26 |
Correct |
39 ms |
31320 KB |
Output is correct |
27 |
Correct |
5 ms |
27228 KB |
Output is correct |
28 |
Correct |
6 ms |
27228 KB |
Output is correct |
29 |
Correct |
9 ms |
27224 KB |
Output is correct |
30 |
Correct |
40 ms |
27484 KB |
Output is correct |
31 |
Correct |
173 ms |
27616 KB |
Output is correct |
32 |
Correct |
6 ms |
27224 KB |
Output is correct |
33 |
Correct |
7 ms |
27228 KB |
Output is correct |
34 |
Correct |
6 ms |
27228 KB |
Output is correct |
35 |
Correct |
10 ms |
27224 KB |
Output is correct |
36 |
Correct |
41 ms |
27472 KB |
Output is correct |
37 |
Correct |
180 ms |
27732 KB |
Output is correct |
38 |
Correct |
10 ms |
28504 KB |
Output is correct |
39 |
Correct |
11 ms |
28508 KB |
Output is correct |
40 |
Correct |
14 ms |
28508 KB |
Output is correct |
41 |
Correct |
52 ms |
28752 KB |
Output is correct |
42 |
Correct |
208 ms |
29044 KB |
Output is correct |
43 |
Correct |
118 ms |
56008 KB |
Output is correct |
44 |
Correct |
119 ms |
56004 KB |
Output is correct |
45 |
Correct |
155 ms |
56004 KB |
Output is correct |
46 |
Correct |
171 ms |
56008 KB |
Output is correct |
47 |
Correct |
434 ms |
56516 KB |
Output is correct |
48 |
Correct |
10 ms |
27740 KB |
Output is correct |
49 |
Correct |
34 ms |
27992 KB |
Output is correct |
50 |
Correct |
141 ms |
28076 KB |
Output is correct |
51 |
Correct |
276 ms |
28496 KB |
Output is correct |
52 |
Correct |
36 ms |
37460 KB |
Output is correct |
53 |
Correct |
69 ms |
37512 KB |
Output is correct |
54 |
Correct |
209 ms |
37716 KB |
Output is correct |
55 |
Correct |
395 ms |
37980 KB |
Output is correct |
56 |
Correct |
178 ms |
83544 KB |
Output is correct |
57 |
Correct |
219 ms |
83536 KB |
Output is correct |
58 |
Correct |
419 ms |
83860 KB |
Output is correct |
59 |
Correct |
660 ms |
84120 KB |
Output is correct |
60 |
Correct |
382 ms |
143916 KB |
Output is correct |
61 |
Correct |
433 ms |
143892 KB |
Output is correct |
62 |
Correct |
678 ms |
144444 KB |
Output is correct |
63 |
Correct |
1087 ms |
144928 KB |
Output is correct |
64 |
Correct |
1881 ms |
144592 KB |
Output is correct |
65 |
Correct |
1743 ms |
123116 KB |
Output is correct |
66 |
Correct |
1854 ms |
129056 KB |
Output is correct |
67 |
Correct |
1734 ms |
128684 KB |
Output is correct |
68 |
Correct |
1847 ms |
128812 KB |
Output is correct |
69 |
Correct |
1729 ms |
125196 KB |
Output is correct |
70 |
Correct |
1388 ms |
96404 KB |
Output is correct |
71 |
Correct |
2256 ms |
137840 KB |
Output is correct |
72 |
Correct |
2333 ms |
137748 KB |
Output is correct |
73 |
Correct |
2306 ms |
137624 KB |
Output is correct |
74 |
Correct |
2206 ms |
137356 KB |
Output is correct |
75 |
Correct |
2086 ms |
132584 KB |
Output is correct |
76 |
Correct |
1656 ms |
100216 KB |
Output is correct |
77 |
Correct |
1614 ms |
118800 KB |
Output is correct |
78 |
Correct |
1537 ms |
119440 KB |
Output is correct |
79 |
Correct |
1801 ms |
119188 KB |
Output is correct |
80 |
Correct |
1854 ms |
119012 KB |
Output is correct |
81 |
Correct |
1712 ms |
115960 KB |
Output is correct |
82 |
Correct |
1401 ms |
92648 KB |
Output is correct |
83 |
Correct |
1699 ms |
118648 KB |
Output is correct |
84 |
Correct |
1726 ms |
118556 KB |
Output is correct |
85 |
Correct |
1646 ms |
118904 KB |
Output is correct |
86 |
Correct |
1818 ms |
118644 KB |
Output is correct |
87 |
Correct |
1673 ms |
116064 KB |
Output is correct |
88 |
Correct |
1343 ms |
92680 KB |
Output is correct |
89 |
Correct |
1855 ms |
126576 KB |
Output is correct |
90 |
Correct |
2108 ms |
133132 KB |
Output is correct |
91 |
Correct |
2370 ms |
137464 KB |
Output is correct |
92 |
Correct |
2468 ms |
136976 KB |
Output is correct |
93 |
Correct |
2476 ms |
134092 KB |
Output is correct |
94 |
Correct |
2118 ms |
128952 KB |
Output is correct |
95 |
Correct |
1568 ms |
115652 KB |
Output is correct |
96 |
Correct |
1610 ms |
115632 KB |
Output is correct |
97 |
Correct |
1715 ms |
115740 KB |
Output is correct |
98 |
Correct |
1847 ms |
118248 KB |
Output is correct |
99 |
Correct |
1629 ms |
115712 KB |
Output is correct |
100 |
Correct |
1691 ms |
115528 KB |
Output is correct |