#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge {
int u, v, w;
int other( int x ) {
return u ^ v ^ x;
}
};
const int MAX_N = 1e5 + 10;
edge edges[MAX_N];
vector<int> adj[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;
}
vector<int> centroids[MAX_N], heads[MAX_N + 1];
unordered_map<int, int> head[MAX_N + 1], leftPos[MAX_N + 1], rightPos[MAX_N + 1];
int crtPos;
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;
centroids[e].push_back( c );
head[c][e] = h;
leftPos[c][e] = crtPos;
dfs( v, u, c, h );
rightPos[c][e] = crtPos - 1;
children++;
}
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;
centroids[e].push_back( c );
heads[c].push_back( e );
head[c][e] = e;
leftPos[c][e] = crtPos;
dfs( v, c, c, e );
rightPos[c][e] = crtPos - 1;
}
isCentroid[c] = true;
for ( int e: adj[c] ) {
int v = edges[e].other( c );
if ( isCentroid[v] )
continue;
decomp( v );
}
}
multiset<int> diameterByCentroid[MAX_N + 1], allDiameters;
struct SegTree {
int ll, rr;
int segTree[4 * MAX_N];
int lazy[4 * MAX_N];
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;
}
void update( int v, int l, int r, int lu, int ru, int 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, int x ) {
update( 0, ll, rr, l, r, x );
}
int query( int v, int l, int r, int lq, int rq ) {
if ( l > rq || r < lq )
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 ) );
}
int query( int l, int r ) {
return query( 0, ll, rr, l, r );
}
} depths;
signed main() {
int n, q, 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 );
}
crtPos = 0;
decomp( 1 );
depths.init( 0, crtPos - 1 );
for ( int c = 1; c <= n; c++ ) {
for ( auto p: head[c] ) {
int e = p.first;
depths.update( leftPos[c][e], rightPos[c][e], edges[e].w );
//printf( "update %d %d %d %d %d\n", c, e, leftPos[c][e], rightPos[c][e], edges[e].w );
}
for ( int h: heads[c] ) {
int maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
diameterByCentroid[c].insert( maxDepth );
//printf( "query %d %d-%d %d %d %d\n", c, edges[h].u, edges[h].v, leftPos[c][h], rightPos[c][h], maxDepth );
}
// printf( "\n" );
int d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
int d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
allDiameters.insert( d1 + d2 );
}
int last = 0;
while ( q-- ) {
int e, w;
cin >> e >> w;
e = (e + last) % (n - 1);
w = (w + last) % m;
//printf( "%d-%d %d\n", edges[e].u, edges[e].v, w );
for ( int c: centroids[e] ) {
int d1, d2, maxDepth;
//printf( "U %d\n", c );
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 ) );
// printf( "%d %d\n", d1, d2 );
//for ( int d: diameterByCentroid[c] )
// printf( "nj %d\n", d );
//for ( int d: allDiameters )
// printf( "l %d\n", d );
int h = head[c][e];
maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
diameterByCentroid[c].erase( diameterByCentroid[c].lower_bound( maxDepth ) );
depths.update( leftPos[c][e], rightPos[c][e], w - edges[e].w );
maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
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";
//printf( "\n\n\n\n" );
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31068 KB |
Output is correct |
2 |
Correct |
14 ms |
31256 KB |
Output is correct |
3 |
Correct |
8 ms |
33112 KB |
Output is correct |
4 |
Correct |
10 ms |
33116 KB |
Output is correct |
5 |
Correct |
10 ms |
31068 KB |
Output is correct |
6 |
Correct |
9 ms |
31068 KB |
Output is correct |
7 |
Correct |
9 ms |
33116 KB |
Output is correct |
8 |
Correct |
13 ms |
31208 KB |
Output is correct |
9 |
Correct |
12 ms |
31064 KB |
Output is correct |
10 |
Correct |
16 ms |
31172 KB |
Output is correct |
11 |
Correct |
13 ms |
31324 KB |
Output is correct |
12 |
Correct |
12 ms |
31576 KB |
Output is correct |
13 |
Correct |
13 ms |
31324 KB |
Output is correct |
14 |
Correct |
13 ms |
31324 KB |
Output is correct |
15 |
Correct |
13 ms |
31320 KB |
Output is correct |
16 |
Correct |
13 ms |
31324 KB |
Output is correct |
17 |
Correct |
10 ms |
33372 KB |
Output is correct |
18 |
Correct |
15 ms |
31324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31068 KB |
Output is correct |
2 |
Correct |
14 ms |
31256 KB |
Output is correct |
3 |
Correct |
8 ms |
33112 KB |
Output is correct |
4 |
Correct |
10 ms |
33116 KB |
Output is correct |
5 |
Correct |
10 ms |
31068 KB |
Output is correct |
6 |
Correct |
9 ms |
31068 KB |
Output is correct |
7 |
Correct |
9 ms |
33116 KB |
Output is correct |
8 |
Correct |
13 ms |
31208 KB |
Output is correct |
9 |
Correct |
12 ms |
31064 KB |
Output is correct |
10 |
Correct |
16 ms |
31172 KB |
Output is correct |
11 |
Correct |
13 ms |
31324 KB |
Output is correct |
12 |
Correct |
12 ms |
31576 KB |
Output is correct |
13 |
Correct |
13 ms |
31324 KB |
Output is correct |
14 |
Correct |
13 ms |
31324 KB |
Output is correct |
15 |
Correct |
13 ms |
31320 KB |
Output is correct |
16 |
Correct |
13 ms |
31324 KB |
Output is correct |
17 |
Correct |
10 ms |
33372 KB |
Output is correct |
18 |
Correct |
15 ms |
31324 KB |
Output is correct |
19 |
Correct |
47 ms |
32220 KB |
Output is correct |
20 |
Correct |
52 ms |
32344 KB |
Output is correct |
21 |
Correct |
48 ms |
32600 KB |
Output is correct |
22 |
Correct |
55 ms |
32792 KB |
Output is correct |
23 |
Correct |
72 ms |
39156 KB |
Output is correct |
24 |
Correct |
81 ms |
41260 KB |
Output is correct |
25 |
Correct |
93 ms |
42320 KB |
Output is correct |
26 |
Correct |
100 ms |
43048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33116 KB |
Output is correct |
2 |
Correct |
9 ms |
33116 KB |
Output is correct |
3 |
Correct |
12 ms |
33112 KB |
Output is correct |
4 |
Correct |
47 ms |
33344 KB |
Output is correct |
5 |
Correct |
204 ms |
34640 KB |
Output is correct |
6 |
Correct |
8 ms |
33116 KB |
Output is correct |
7 |
Correct |
8 ms |
33372 KB |
Output is correct |
8 |
Correct |
9 ms |
33368 KB |
Output is correct |
9 |
Correct |
13 ms |
33372 KB |
Output is correct |
10 |
Correct |
55 ms |
33636 KB |
Output is correct |
11 |
Correct |
229 ms |
34952 KB |
Output is correct |
12 |
Correct |
14 ms |
34908 KB |
Output is correct |
13 |
Correct |
15 ms |
34908 KB |
Output is correct |
14 |
Correct |
19 ms |
35000 KB |
Output is correct |
15 |
Correct |
64 ms |
35244 KB |
Output is correct |
16 |
Correct |
273 ms |
36412 KB |
Output is correct |
17 |
Correct |
170 ms |
67828 KB |
Output is correct |
18 |
Correct |
172 ms |
67860 KB |
Output is correct |
19 |
Correct |
193 ms |
67788 KB |
Output is correct |
20 |
Correct |
239 ms |
69092 KB |
Output is correct |
21 |
Correct |
549 ms |
70900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
34652 KB |
Output is correct |
2 |
Correct |
60 ms |
34652 KB |
Output is correct |
3 |
Correct |
245 ms |
35160 KB |
Output is correct |
4 |
Correct |
474 ms |
36012 KB |
Output is correct |
5 |
Correct |
102 ms |
50516 KB |
Output is correct |
6 |
Correct |
190 ms |
50504 KB |
Output is correct |
7 |
Correct |
496 ms |
51260 KB |
Output is correct |
8 |
Correct |
956 ms |
52032 KB |
Output is correct |
9 |
Runtime error |
388 ms |
269376 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
751 ms |
392480 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31068 KB |
Output is correct |
2 |
Correct |
14 ms |
31256 KB |
Output is correct |
3 |
Correct |
8 ms |
33112 KB |
Output is correct |
4 |
Correct |
10 ms |
33116 KB |
Output is correct |
5 |
Correct |
10 ms |
31068 KB |
Output is correct |
6 |
Correct |
9 ms |
31068 KB |
Output is correct |
7 |
Correct |
9 ms |
33116 KB |
Output is correct |
8 |
Correct |
13 ms |
31208 KB |
Output is correct |
9 |
Correct |
12 ms |
31064 KB |
Output is correct |
10 |
Correct |
16 ms |
31172 KB |
Output is correct |
11 |
Correct |
13 ms |
31324 KB |
Output is correct |
12 |
Correct |
12 ms |
31576 KB |
Output is correct |
13 |
Correct |
13 ms |
31324 KB |
Output is correct |
14 |
Correct |
13 ms |
31324 KB |
Output is correct |
15 |
Correct |
13 ms |
31320 KB |
Output is correct |
16 |
Correct |
13 ms |
31324 KB |
Output is correct |
17 |
Correct |
10 ms |
33372 KB |
Output is correct |
18 |
Correct |
15 ms |
31324 KB |
Output is correct |
19 |
Correct |
47 ms |
32220 KB |
Output is correct |
20 |
Correct |
52 ms |
32344 KB |
Output is correct |
21 |
Correct |
48 ms |
32600 KB |
Output is correct |
22 |
Correct |
55 ms |
32792 KB |
Output is correct |
23 |
Correct |
72 ms |
39156 KB |
Output is correct |
24 |
Correct |
81 ms |
41260 KB |
Output is correct |
25 |
Correct |
93 ms |
42320 KB |
Output is correct |
26 |
Correct |
100 ms |
43048 KB |
Output is correct |
27 |
Correct |
7 ms |
33116 KB |
Output is correct |
28 |
Correct |
9 ms |
33116 KB |
Output is correct |
29 |
Correct |
12 ms |
33112 KB |
Output is correct |
30 |
Correct |
47 ms |
33344 KB |
Output is correct |
31 |
Correct |
204 ms |
34640 KB |
Output is correct |
32 |
Correct |
8 ms |
33116 KB |
Output is correct |
33 |
Correct |
8 ms |
33372 KB |
Output is correct |
34 |
Correct |
9 ms |
33368 KB |
Output is correct |
35 |
Correct |
13 ms |
33372 KB |
Output is correct |
36 |
Correct |
55 ms |
33636 KB |
Output is correct |
37 |
Correct |
229 ms |
34952 KB |
Output is correct |
38 |
Correct |
14 ms |
34908 KB |
Output is correct |
39 |
Correct |
15 ms |
34908 KB |
Output is correct |
40 |
Correct |
19 ms |
35000 KB |
Output is correct |
41 |
Correct |
64 ms |
35244 KB |
Output is correct |
42 |
Correct |
273 ms |
36412 KB |
Output is correct |
43 |
Correct |
170 ms |
67828 KB |
Output is correct |
44 |
Correct |
172 ms |
67860 KB |
Output is correct |
45 |
Correct |
193 ms |
67788 KB |
Output is correct |
46 |
Correct |
239 ms |
69092 KB |
Output is correct |
47 |
Correct |
549 ms |
70900 KB |
Output is correct |
48 |
Correct |
17 ms |
34652 KB |
Output is correct |
49 |
Correct |
60 ms |
34652 KB |
Output is correct |
50 |
Correct |
245 ms |
35160 KB |
Output is correct |
51 |
Correct |
474 ms |
36012 KB |
Output is correct |
52 |
Correct |
102 ms |
50516 KB |
Output is correct |
53 |
Correct |
190 ms |
50504 KB |
Output is correct |
54 |
Correct |
496 ms |
51260 KB |
Output is correct |
55 |
Correct |
956 ms |
52032 KB |
Output is correct |
56 |
Runtime error |
388 ms |
269376 KB |
Execution killed with signal 11 |
57 |
Halted |
0 ms |
0 KB |
- |