#include <bits/stdc++.h>
using namespace std;
struct query {
int u, v, w;
bool operator < ( const query &q ) const {
return w < q.w;
}
};
const int INF = (1 << 30);
const int MAX_N = 7e4 + 1;
const int MAX_LOG_N = 16;
const int undef = -1;
bool used[MAX_N];
int depth[MAX_N], parent[MAX_LOG_N + 1][MAX_N], asc[MAX_N], queryMin[MAX_N], queryMax[MAX_N], value[MAX_N];
vector<int> edges[MAX_N];
vector<query> mins, maxs;
void dfs( int u, int p ) {
depth[u] = depth[p] + 1;
parent[0][u] = p;
for ( int v: edges[u] ) {
if ( v == p )
continue;
dfs( v, u );
}
}
int lca( int u, int v ) {
if ( depth[u] > depth[v] )
swap( u, v );
for ( int p = MAX_LOG_N; p >= 0; p-- ) {
if ( depth[parent[p][v]] >= depth[u] )
v = parent[p][v];
}
if ( u == v )
return u;
for ( int p = MAX_LOG_N; p >= 0; p-- ) {
if ( parent[p][u] != parent[p][v] ) {
u = parent[p][u];
v = parent[p][v];
}
}
return parent[0][v];
}
int findParent( int u, int d ) {
if ( d < 0 )
return undef;
for ( int p = MAX_LOG_N; p >= 0; p-- ) {
if ( d >= (1 << p) ) {
u = parent[p][u];
d -= (1 << p);
}
}
return u;
}
void init( int n ) {
for ( int p = 1; p <= MAX_LOG_N; p++ ) {
for ( int u = 1; u <= n; u++ )
parent[p][u] = parent[p - 1][parent[p - 1][u]];
}
}
struct MATCH {
const int NIL = 0;
int n, m;
int pairU[MAX_N + 1], pairV[MAX_N + 1], dist[MAX_N + 1];
vector <int> edges[MAX_N + 1];
void init( int _n, int _m ) {
n = _n;
m = _m;
}
void add_edge( int u, int v ) {
edges[u].push_back( v );
}
bool bfs() {
int u;
queue <int> q;
dist[NIL] = INF;
for ( u = 1; u <= n; u++ ) {
if ( pairU[u] == NIL ) {
dist[u] = 0;
q.push( u );
} else
dist[u] = INF;
}
while ( !q.empty() ) {
u = q.front();
q.pop();
if ( dist[u] < dist[NIL] ) {
for ( int v: edges[u] ) {
if ( dist[pairV[v]] == INF ) {
dist[pairV[v]] = dist[u] + 1;
q.push( pairV[v] );
}
}
}
}
return dist[NIL] != INF;
}
bool dfs( int u ) {
if ( u == NIL )
return true;
for ( int v: edges[u] ) {
if ( dist[pairV[v]] == dist[u] + 1 && dfs( pairV[v] ) ) {
pairU[u] = v;
pairV[v] = u;
return true;
}
}
dist[u] = INF;
return false;
}
void maxMatch() {
int maxMatch, u, v;
for ( u = 0; u <= n; u++ )
pairU[u] = NIL;
for ( v = 0; v <= m; v++ )
pairV[v] = NIL;
while ( bfs() ) {
for ( u = 1; u <= n; u++ ) {
if ( pairU[u] == NIL )
dfs( u );
}
}
}
};
MATCH match;
struct info {
int minn, maxx;
info operator + ( const info &x ) const {
return { min( minn, x.minn ), max( maxx, x.maxx ) };
}
};
struct SegTree {
info segTree[4 * MAX_N];
info lazy[4 * MAX_N];
void init() {
for ( int v = 0; v < 4 * MAX_N; v++ ) {
lazy[v] = segTree[v] = { INF, -INF };
}
}
void propag( int v, int l, int r ) {
segTree[v] = segTree[v] + lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
lazy[v * 2 + 2] = lazy[v * 2 + 2] + lazy[v];
}
}
void update( int v, int l, int r, int lu, int ru, info 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] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
}
info query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return { INF, -INF };
if ( lq <= l && r <= rq )
return segTree[v];
int mid = (l + r) / 2;
return query( v * 2 + 1, l, mid, lq, rq ) + query( v * 2 + 2, mid + 1, r, lq, rq );
}
};
struct HPD {
int n, curPos;
int sz[MAX_N], parent[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[MAX_N];
SegTree aint;
void dfs( int u, int p ) {
int maxSz = -1;
parent[u] = p;
depth[u] = depth[p] + 1;
sz[u] = 1;
heavy[u] = undef;
for ( int v: edges[u] ) {
if ( v == p )
continue;
dfs( v, u );
sz[u] += sz[v];
if ( sz[v] > maxSz ) {
maxSz = sz[v];
heavy[u] = v;
}
}
}
void decomp( int u, int p, int h ) {
head[u] = h;
leftPos[u] = ++curPos;
if ( heavy[u] != undef )
decomp( heavy[u], u, h );
for ( int v: edges[u] ) {
if ( v == p || v == heavy[u] )
continue;
decomp( v, u, v );
}
}
void init( int _n ) {
n = _n;
aint.init();
dfs( 1, 0 );
decomp( 1, 0, 1 );
}
void updatePath( int u, int v, info x ) {
while ( head[u] != head[v] ) {
if ( depth[head[u]] < depth[head[v]] )
swap( u, v );
aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
u = parent[head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
aint.update( 0, 1, n, leftPos[u], leftPos[v], x );
}
info queryVertex( int u ) {
return aint.query( 0, 1, n, leftPos[u], leftPos[u] );
}
};
HPD arb;
unordered_map<int, int> indx;
int main() {
int n, k;
cin >> n;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
edges[u].push_back( v );
edges[v].push_back( u );
}
dfs( 1, 0 );
init( n );
cin >> k;
for ( int i = 0; i < k; i++ ) {
char ch;
int u, v, w;
cin >> ch >> u >> v >> w;
if ( ch == 'm' )
mins.push_back( { u, v, w } );
else
maxs.push_back( { u, v, w } );
}
arb.init( n );
for ( int i = 0; i < mins.size(); i++ ) {
indx[mins[i].w] = i;
int u = mins[i].u, v = mins[i].v;
int l = lca( u, v );
int a = findParent( u, depth[u] - depth[l] - 1 );
int b = findParent( v, depth[v] - depth[l] - 1 );
if ( a != undef )
arb.updatePath( u, a, { INF, mins[i].w, } );
if ( b != undef )
arb.updatePath( v, b, { INF, mins[i].w } );
}
for ( int i = 0; i < maxs.size(); i++ ) {
indx[maxs[i].w] = i;
int u = maxs[i].u, v = maxs[i].v;
int l = lca( u, v );
int a = findParent( u, depth[u] - depth[l] - 1 );
int b = findParent( v, depth[v] - depth[l] - 1 );
if ( a != undef )
arb.updatePath( u, a, { maxs[i].w, -INF } );
if ( b != undef )
arb.updatePath( v, b, { maxs[i].w, -INF } );
}
indx[INF] = indx[-INF] = -1;
for ( int u = 2; u <= n; u++ ) {
queryMin[u] = indx[arb.queryVertex( u ).maxx];
queryMax[u] = indx[arb.queryVertex( u ).minn];
//printf( "%d %d\n", arb.queryVertex( u ).maxx, arb.queryVertex( u ).minn );
}
match.init( k, n - 1 );
for ( int u = 2; u <= n; u++ ) {
if ( queryMin[u] != -1 )
match.add_edge( queryMin[u] + 1, u - 1 );
if ( queryMax[u] != -1 )
match.add_edge( mins.size() + queryMax[u] + 1, u - 1 );
}
match.maxMatch();
for ( int u = 2; u <= n; u++ )
value[u] = undef;
for ( int i = 0; i < mins.size(); i++ )
value[match.pairU[i + 1] + 1] = mins[i].w;
for ( int i = 0; i < maxs.size(); i++ )
value[match.pairU[mins.size() + i + 1] + 1] = maxs[i].w;
for ( int u = 2; u <= n; u++ ) {
if ( value[u] == undef ) {
if ( queryMin[u] != undef )
value[u] = mins[queryMin[u]].w;
else if ( queryMax[u] != undef )
value[u] = maxs[queryMax[u]].w;
else
value[u] = 0;
}
cout << u << " " << parent[0][u] << " " << value[u] << "\n";
}
return 0;
}
Compilation message
minmaxtree.cpp: In member function 'void MATCH::maxMatch()':
minmaxtree.cpp:134:13: warning: unused variable 'maxMatch' [-Wunused-variable]
134 | int maxMatch, u, v;
| ^~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:301:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
301 | for ( int i = 0; i < mins.size(); i++ ) {
| ~~^~~~~~~~~~~~~
minmaxtree.cpp:312:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
312 | for ( int i = 0; i < maxs.size(); i++ ) {
| ~~^~~~~~~~~~~~~
minmaxtree.cpp:342:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
342 | for ( int i = 0; i < mins.size(); i++ )
| ~~^~~~~~~~~~~~~
minmaxtree.cpp:344:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
344 | for ( int i = 0; i < maxs.size(); i++ )
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8096 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
291 ms |
37120 KB |
Output is correct |
| 2 |
Correct |
299 ms |
27664 KB |
Output is correct |
| 3 |
Correct |
282 ms |
34836 KB |
Output is correct |
| 4 |
Correct |
287 ms |
42740 KB |
Output is correct |
| 5 |
Correct |
283 ms |
33060 KB |
Output is correct |
| 6 |
Correct |
283 ms |
30084 KB |
Output is correct |
| 7 |
Correct |
250 ms |
28228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
21648 KB |
Output is correct |
| 2 |
Correct |
162 ms |
23056 KB |
Output is correct |
| 3 |
Correct |
157 ms |
33968 KB |
Output is correct |
| 4 |
Correct |
160 ms |
39152 KB |
Output is correct |
| 5 |
Correct |
167 ms |
25724 KB |
Output is correct |
| 6 |
Correct |
184 ms |
27196 KB |
Output is correct |
| 7 |
Correct |
179 ms |
23440 KB |
Output is correct |
| 8 |
Correct |
166 ms |
23244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8096 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
291 ms |
37120 KB |
Output is correct |
| 6 |
Correct |
299 ms |
27664 KB |
Output is correct |
| 7 |
Correct |
282 ms |
34836 KB |
Output is correct |
| 8 |
Correct |
287 ms |
42740 KB |
Output is correct |
| 9 |
Correct |
283 ms |
33060 KB |
Output is correct |
| 10 |
Correct |
283 ms |
30084 KB |
Output is correct |
| 11 |
Correct |
250 ms |
28228 KB |
Output is correct |
| 12 |
Correct |
160 ms |
21648 KB |
Output is correct |
| 13 |
Correct |
162 ms |
23056 KB |
Output is correct |
| 14 |
Correct |
157 ms |
33968 KB |
Output is correct |
| 15 |
Correct |
160 ms |
39152 KB |
Output is correct |
| 16 |
Correct |
167 ms |
25724 KB |
Output is correct |
| 17 |
Correct |
184 ms |
27196 KB |
Output is correct |
| 18 |
Correct |
179 ms |
23440 KB |
Output is correct |
| 19 |
Correct |
166 ms |
23244 KB |
Output is correct |
| 20 |
Correct |
315 ms |
28256 KB |
Output is correct |
| 21 |
Correct |
300 ms |
26836 KB |
Output is correct |
| 22 |
Correct |
294 ms |
26924 KB |
Output is correct |
| 23 |
Correct |
288 ms |
26784 KB |
Output is correct |
| 24 |
Correct |
273 ms |
40628 KB |
Output is correct |
| 25 |
Correct |
280 ms |
46400 KB |
Output is correct |
| 26 |
Correct |
265 ms |
44712 KB |
Output is correct |
| 27 |
Correct |
334 ms |
39072 KB |
Output is correct |
| 28 |
Correct |
308 ms |
29856 KB |
Output is correct |
| 29 |
Correct |
303 ms |
30260 KB |
Output is correct |
| 30 |
Correct |
284 ms |
28684 KB |
Output is correct |
| 31 |
Correct |
296 ms |
28208 KB |
Output is correct |
| 32 |
Correct |
296 ms |
28432 KB |
Output is correct |
| 33 |
Correct |
286 ms |
27588 KB |
Output is correct |
| 34 |
Correct |
302 ms |
27668 KB |
Output is correct |
| 35 |
Correct |
282 ms |
27076 KB |
Output is correct |
