#include<bits/stdc++.h>
using namespace std ;
#define MAXN 100007
#define LOG 20
int n ;
int a[ MAXN ] ;
pair < int , int > edges[ MAXN ] ;
vector < int > v[ MAXN ] ;
int pos_in_tree[ MAXN ] ;
int LCA[ MAXN ][ LOG ] ;
int subtree[ MAXN ] , heavy[ MAXN ] ;
int root[ MAXN ] ;
void dfs ( int vertex ) {
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
}
subtree[ vertex ] = 1 ;
int mx = -1 ;
heavy[ vertex ] = 0 ;
for ( auto x : v[ vertex ] ) {
LCA[ x ][ 0 ] = vertex ;
dfs ( x ) ;
subtree[ vertex ] += subtree[ x ] ;
if ( mx < subtree[ x ] ) {
mx = subtree[ x ] ;
heavy[ vertex ] = x ;
}
}
}
class Tree {
public :
int tr[ 4 * MAXN ] , lazy[ 4 * MAXN ] ;
void push_lazy ( int where , int IL , int IR ) {
if ( lazy[ where ] == 0 ) { return ; }
tr[ where ] = lazy[ where ] ;
if ( IL != IR ) {
lazy[ 2 * where ] = lazy[ where ] ;
lazy[ 2 * where + 1 ] = lazy[ where ] ;
}
lazy[ where ] = 0 ;
}
void init ( int where , int IL , int IR ) {
tr[ where ] = lazy[ where ] = 0 ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void update ( int where , int IL , int IR , int CURL , int CURR , int nw ) {
push_lazy ( where , IL , IR ) ;
if ( IL > IR || CURL > CURR ) { return ; }
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
lazy[ where ] = nw ;
push_lazy ( where , IL , IR ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , CURL , CURR , nw ) ;
update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , nw ) ;
}
int query ( int where , int IL , int IR , int pos ) {
push_lazy ( where , IL , IR ) ;
if ( IL == IR ) { return tr[ where ] ; }
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) { return query ( 2 * where , IL , mid , pos ) ; }
return query ( 2 * where + 1 , mid + 1 , IR , pos ) ;
}
};
Tree w ;
void input ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ] ;
}
for ( int i = 1 ; i < n ; ++ i ) {
cin >> edges[ i ].first >> edges[ i ].second ;
v[ edges[ i ].first ].push_back ( edges[ i ].second ) ;
}
}
stack < pair < int , int > > s ;
pair < int , int > srt[ MAXN ] ;
pair < int , int > aux[ MAXN ] ;
long long f ( int l , int r ) {
if ( l == r ) { return 0 ; }
int mid = ( l + r ) / 2 ;
long long ret = f ( l , mid ) + f ( mid + 1 , r ) ;
int pos1 , pos2 ;
pos1 = l , pos2 = mid + 1 ;
int tp = l - 1 ;
long long sm_l = 0 ;
for ( int i = l ; i <= mid ; ++ i ) {
sm_l += srt[ i ].second ;
}
while ( pos1 <= mid || pos2 <= r ) {
if ( pos1 > mid ) {
aux[ ++ tp ] = srt[ pos2 ++ ] ;
}
else if ( pos2 > r ) {
aux[ ++ tp ] = srt[ pos1 ++ ] ;
}
else {
if ( srt[ pos1 ].first <= srt[ pos2 ].first ) {
aux[ ++ tp ] = srt[ pos1 ] ;
sm_l -= srt[ pos1 ++ ].second ;
}
else {
aux[ ++ tp ] = srt[ pos2 ++ ] ;
ret += sm_l ;
}
}
}
for ( int i = l ; i <= r ; ++ i ) {
srt[ i ] = aux[ i ] ;
}
return ret ;
}
void solve ( ) {
dfs ( 1 ) ;
int tp = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( heavy[ LCA[ i ][ 0 ] ] != i ) {
int x = i ;
while ( x != 0 ) {
pos_in_tree[ x ] = ++ tp ;
root[ x ] = i ;
x = heavy[ x ] ;
}
}
}
w.init ( 1 , 1 , n ) ;
w.update ( 1 , 1 , n , 1 , 1 , 1 ) ;
for ( int i = 1 ; i < n ; ++ i ) {
int wh = edges[ i ].first ;
while ( wh > 0 ) {
int sr = w.query ( 1 , 1 , n , pos_in_tree[ wh ] ) ;
int cnt = 1 ;
for ( int j = LOG - 1 ; j >= 0 ; -- j ) {
if ( LCA[ wh ][ j ] > 0 && w.query ( 1 , 1 , n , pos_in_tree[ LCA[ wh ][ j ] ] ) == sr ) {
wh = LCA[ wh ][ j ] ;
cnt += ( 1 << j ) ;
}
}
s.push ( { a[ sr ] , cnt } ) ;
wh = LCA[ wh ][ 0 ] ;
}
tp = 0 ;
while ( s.empty ( ) == false ) {
srt[ ++ tp ] = s.top ( ) ;
s.pop ( ) ;
}
cout << f ( 1 , tp ) << "\n" ;
wh = edges[ i ].second ;
while ( wh > 0 ) {
w.update ( 1 , 1 , n , pos_in_tree[ root[ wh ] ] , pos_in_tree[ wh ] , edges[ i ].second ) ;
wh = LCA[ root[ wh ] ][ 0 ] ;
}
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
