#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 70007 ;
const int inf = 1e9 + 7 ;
int n ;
vector < int > v[ MAXN ] ;
int prv[ MAXN ] , lvl[ MAXN ] ;
int subtree[ MAXN ] , heavy[ MAXN ] ;
int pos_in_tree[ MAXN ] , root[ MAXN ] ;
struct query {
int type , x , y ;
int val ;
};
query qlist[ MAXN ] ;
void dfs ( int x , int lst ) {
subtree[ x ] = 1 ;
int mx = -1 ;
for ( auto y : v[ x ] ) {
if ( y == lst ) { continue ; }
prv[ y ] = x ;
lvl[ y ] = lvl[ x ] + 1 ;
dfs ( y , x ) ;
subtree[ x ] += subtree[ y ] ;
if ( mx < subtree[ y ] ) {
mx = subtree[ y ] ;
heavy[ x ] = y ;
}
}
}
struct node {
pair < int , int > mn , mx ;
node ( ) {
mn = { -inf , 0 } ;
mx = { inf , 0 } ;
}
};
node tr[ 4 * MAXN ] ;
void update ( int where , int IL , int IR , int CURL , int CURR , int sr , int id , int type ) {
if ( IL > IR || CURL > CURR ) { return ; }
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
if ( type == 0 ) {
if ( tr[ where ].mn.fi < sr ) {
tr[ where ].mn = { sr , id } ;
}
}
else {
if ( sr < tr[ where ].mx.fi ) {
tr[ where ].mx = { sr , id } ;
}
}
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , CURL , CURR , sr , id , type ) ;
update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , sr , id , type ) ;
}
node query ( int where , int IL , int IR , int pos ) {
if ( IL == IR ) { return tr[ where ] ; }
node ret = node ( ) ;
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) { ret = query ( 2 * where , IL , mid , pos ) ; }
else { ret = query ( 2 * where + 1 , mid + 1 , IR , pos ) ; }
if ( ret.mn.fi < tr[ where ].mn.fi ) {
ret.mn = tr[ where ].mn ;
}
if ( ret.mx.fi > tr[ where ].mx.fi ) {
ret.mx = tr[ where ].mx ;
}
return ret ;
}
int cnt[ MAXN ] ;
priority_queue < pair < int , int > > q ;
vector < int > cont[ MAXN ] ;
int ans[ MAXN ] ;
int idle[ MAXN ] ;
vector < pair < int , int > > srt ;
pair < int , int > hh[ MAXN ] ;
void solve ( ) {
cin >> n ;
for ( int i = 1 , x , y ; i < n ; ++ i ) {
cin >> x >> y ;
v[ x ].push_back ( y ) ;
v[ y ].push_back ( x ) ;
}
dfs ( 1 , -1 ) ;
int tp = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( i == 1 || heavy[ prv[ i ] ] != i ) {
int x = i ;
while ( x != 0 ) {
root[ x ] = i ;
pos_in_tree[ x ] = ++ tp ;
x = heavy[ x ] ;
}
}
}
int q ;
cin >> q ;
for ( int i = 1 ; i <= q ; ++ i ) {
char c ;
cin >> c ;
if ( c == 'm' ) { qlist[ i ].type = 0 ; }
else { qlist[ i ].type = 1 ; }
cin >> qlist[ i ].x >> qlist[ i ].y >> qlist[ i ].val ;
int x = qlist[ i ].x , y = qlist[ i ].y ;
while ( root[ x ] != root[ y ] ) {
if ( lvl[ root[ x ] ] < lvl[ root[ y ] ] ) { swap ( x , y ) ; }
update ( 1 , 1 , n , pos_in_tree[ root[ x ] ] , pos_in_tree[ x ] , qlist[ i ].val , i , qlist[ i ].type ) ;
x = prv[ root[ x ] ] ;
}
if ( pos_in_tree[ x ] > pos_in_tree[ y ] ) { swap ( x , y ) ; }
update ( 1 , 1 , n , pos_in_tree[ x ] + 1 , pos_in_tree[ y ] , qlist[ i ].val , i , qlist[ i ].type ) ;
}
for ( int i = 2 ; i <= n ; ++ i ) {
node ret = query ( 1 , 1 , n , pos_in_tree[ i ] ) ;
hh[ i ] = { ret.mn.se , ret.mx.se } ;
++ cnt[ ret.mn.se ] ;
++ cnt[ ret.mx.se ] ;
if ( ret.mn.se > 0 ) {
cont[ ret.mn.se ].push_back ( i ) ;
idle[ i ] = ret.mn.fi ;
}
if ( ret.mx.se > 0 ) {
cont[ ret.mx.se ].push_back ( i ) ;
idle[ i ] = ret.mx.fi ;
}
}
cnt[ 0 ] += MAXN ;
for ( int i = 1 ; i <= n ; ++ i ) {
ans[ i ] = -inf ;
}
for ( int i = 1 ; i <= q ; ++ i ) {
srt.push_back ( { cnt[ i ] , i } ) ;
}
sort ( srt.begin ( ) , srt.end ( ) ) ;
for ( auto [ foo , wh ] : srt ) {
int mx_oth = -1 , aux = 0 ;
for ( auto cand : cont[ wh ] ) {
if ( ans[ cand ] == -inf ) {
int oth = hh[ cand ].first + hh[ cand ].second - wh ;
if ( mx_oth < cnt[ oth ] ) {
mx_oth = cnt[ oth ] ;
aux = cand ;
}
}
}
ans[ aux ] = qlist[ wh ].val ;
int oth = hh[ aux ].first + hh[ aux ].second - wh ;
-- cnt[ oth ] ;
cnt[ wh ] += MAXN ;
}
for ( int i = 2 ; i <= n ; ++ i ) {
cout << prv[ i ] << " " << i << " " ;
if ( ans[ i ] != -inf ) { cout << ans[ i ] << "\n" ; }
else { cout << idle[ i ] << "\n" ; }
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
Compilation message
minmaxtree.cpp: In function 'void solve()':
minmaxtree.cpp:155:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
155 | for ( auto [ foo , wh ] : srt ) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8048 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
22240 KB |
Output is correct |
| 2 |
Correct |
160 ms |
18496 KB |
Output is correct |
| 3 |
Correct |
115 ms |
20352 KB |
Output is correct |
| 4 |
Correct |
132 ms |
23260 KB |
Output is correct |
| 5 |
Correct |
130 ms |
19956 KB |
Output is correct |
| 6 |
Correct |
114 ms |
19140 KB |
Output is correct |
| 7 |
Correct |
114 ms |
18504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
15816 KB |
Output is correct |
| 2 |
Correct |
84 ms |
17236 KB |
Output is correct |
| 3 |
Correct |
93 ms |
20440 KB |
Output is correct |
| 4 |
Correct |
87 ms |
22296 KB |
Output is correct |
| 5 |
Correct |
94 ms |
18108 KB |
Output is correct |
| 6 |
Correct |
104 ms |
18764 KB |
Output is correct |
| 7 |
Correct |
90 ms |
17484 KB |
Output is correct |
| 8 |
Correct |
100 ms |
17472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8048 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 5 |
Correct |
127 ms |
22240 KB |
Output is correct |
| 6 |
Correct |
160 ms |
18496 KB |
Output is correct |
| 7 |
Correct |
115 ms |
20352 KB |
Output is correct |
| 8 |
Correct |
132 ms |
23260 KB |
Output is correct |
| 9 |
Correct |
130 ms |
19956 KB |
Output is correct |
| 10 |
Correct |
114 ms |
19140 KB |
Output is correct |
| 11 |
Correct |
114 ms |
18504 KB |
Output is correct |
| 12 |
Correct |
81 ms |
15816 KB |
Output is correct |
| 13 |
Correct |
84 ms |
17236 KB |
Output is correct |
| 14 |
Correct |
93 ms |
20440 KB |
Output is correct |
| 15 |
Correct |
87 ms |
22296 KB |
Output is correct |
| 16 |
Correct |
94 ms |
18108 KB |
Output is correct |
| 17 |
Correct |
104 ms |
18764 KB |
Output is correct |
| 18 |
Correct |
90 ms |
17484 KB |
Output is correct |
| 19 |
Correct |
100 ms |
17472 KB |
Output is correct |
| 20 |
Runtime error |
136 ms |
36976 KB |
Execution killed with signal 11 |
| 21 |
Halted |
0 ms |
0 KB |
- |
