QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#288629 | #7610. Bus Lines | Sorting | RE | 3ms | 37296kb | C++20 | 9.2kb | 2023-12-23 08:29:57 | 2023-12-23 08:29:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector<int> vi;
typedef vector < long long > vl ;
typedef unsigned int uint ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAXN = 2e5 + 7 ;
const int LOG = 20 ;
int n , m ;
vector < int > v[ MAXN ] ;
pii a[ MAXN ] ;
int subtree[ MAXN ] ;
vector < int > at_lca[ MAXN ] ;
vector < int > ending_at[ MAXN ] ;
int LCA[ MAXN ][ LOG ] , lvl[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] , tp ;
void init ( int x , int prv ) {
st[ x ] = ++ tp ;
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ x ][ i ] = LCA[ LCA[ x ][ i - 1 ] ][ i - 1 ] ;
}
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
LCA[ y ][ 0 ] = x ;
lvl[ y ] = lvl[ x ] + 1 ;
init ( y , x ) ;
}
en[ x ] = tp ;
}
ll down[ MAXN ] , up[ MAXN ] ; // down[ x ] - edge above x
ll child_sum[ MAXN ] ;
class Tree {
public :
ll tr[ 4 * MAXN ] ;
void init ( int w , int l , int r ) {
tr[ w ] = 0 ;
if ( l == r ) { return ; }
int mid = ( l + r ) / 2 ;
init ( 2 * w , l , mid ) ;
init ( 2 * w + 1 , mid + 1 , r ) ;
}
void update ( int w , int l , int r , int st , int en , ll add ) {
if ( l > r || st > en ) { return ; }
if ( r < st || en < l ) { return ; }
if ( st <= l && r <= en ) {
tr[ w ] += add ;
return ;
}
int mid = ( l + r ) / 2 ;
update ( 2 * w , l , mid , st , en , add ) ;
update ( 2 * w + 1 , mid + 1 , r , st , en , add ) ;
}
ll query ( int w , int l , int r , int pos ) {
if ( pos < l || r < pos ) { return 0 ; }
ll ret = tr[ w ] ;
if ( l == r ) { return ret ; }
int mid = ( l + r ) / 2 ;
if ( pos <= mid ) { ret += query ( 2 * w , l , mid , pos ) ; }
else { ret += query ( 2 * w + 1 , mid + 1 , r , pos ) ; }
return ret ;
}
};
Tree w ;
int get_lca ( int x , int y ) {
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( ( lvl[ x ] - ( 1 << i ) ) >= lvl[ y ] ) { x = LCA[ x ][ i ] ; }
if ( ( lvl[ y ] - ( 1 << i ) ) >= lvl[ x ] ) { y = LCA[ y ][ i ] ; }
}
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
x = LCA[ x ][ i ] ;
y = LCA[ y ][ i ] ;
}
}
if ( x != y ) { x = LCA[ x ][ 0 ] ; }
return x ;
}
ll path_val ( int x , int y ) {
int aux = get_lca ( x , y ) ;
// printf ( "path query %d %d -- %lld\n" , x , y , w.query ( 1 , 1 , n , st[ x ] ) + w.query ( 1 , 1 , n , st[ y ] ) - 2 * w.query ( 1 , 1 , n , st[ aux ] ) ) ;
return w.query ( 1 , 1 , n , st[ x ] ) + w.query ( 1 , 1 , n , st[ y ] ) - 2 * w.query ( 1 , 1 , n , st[ aux ] ) ;
}
ll hh[ MAXN ] ;
multiset < pii > s[ MAXN ] ;
void add_elem ( int wh , int x ) {
if ( s[ wh ].empty ( ) == true ) {
s[ wh ].insert ( { st[ x ] , x } ) ;
return ;
}
auto nxt = s[ wh ].lower_bound ( { st[ x ] , x } ) ;
auto prv = nxt ;
if ( nxt == s[ wh ].end ( ) ) { nxt = s[ wh ].begin ( ) ; }
if ( prv == s[ wh ].begin ( ) ) { prv = s[ wh ].end ( ) ; -- prv ; }
else { -- prv ; }
hh[ wh ] -= path_val ( prv->se , nxt->se ) ;
hh[ wh ] += path_val ( prv->se , x ) ;
hh[ wh ] += path_val ( x , nxt->se ) ;
s[ wh ].insert ( { st[ x ] , x } ) ;
}
void rem_elem ( int wh , int x ) {
if ( s[ wh ].size ( ) == 1 ) {
s[ wh ].clear ( ) ;
return ;
}
auto it = s[ wh ].find ( { st[ x ] , x } ) ;
auto nxt = it , prv = it ;
++ nxt ;
if ( nxt == s[ wh ].end ( ) ) { nxt = s[ wh ].begin ( ) ; }
if ( prv == s[ wh ].begin ( ) ) { prv = s[ wh ].end ( ) ; -- prv ; }
else { -- prv ; }
hh[ wh ] -= path_val ( prv->se , x ) ;
hh[ wh ] -= path_val ( x , nxt->se ) ;
hh[ wh ] += path_val ( prv->se , nxt->se ) ;
s[ wh ].erase ( it ) ;
}
void dfs_down ( int x , int prv ) {
int wh = 0 ;
subtree[ x ] = 1 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_down ( y , x ) ;
subtree[ x ] += subtree[ y ] ;
child_sum[ x ] += down[ y ] ;
if ( s[ y ].size ( ) > s[ wh ].size ( ) ) { wh = y ; }
}
swap ( s[ wh ] , s[ x ] ) ;
hh[ x ] = hh[ wh ] ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto [ pos , val ] : s[ y ] ) {
add_elem ( x , val ) ;
}
}
for ( auto id : at_lca[ x ] ) {
if ( a[ id ].fi != x ) { rem_elem ( x , a[ id ].fi ) ; }
if ( a[ id ].se != x ) { rem_elem ( x , a[ id ].se ) ; }
}
/**
printf ( "-- %d --> %d %lld %lld\n" , x , subtree[ x ] , hh[ x ] / 2 , child_sum[ x ] ) ;
for ( auto [ pos , val ] : s[ x ] ) {
printf ( "%d " , val ) ;
}
printf ( "\n" ) ;
**/
down[ x ] = subtree[ x ] ;
if ( s[ x ].empty ( ) == false ) {
add_elem ( x , x ) ;
down[ x ] += hh[ x ] / 2 + child_sum[ x ] ;
rem_elem ( x , x ) ;
}
else { down[ x ] += child_sum[ x ] ; }
// if ( x != 1 ) {
w.update ( 1 , 1 , n , st[ x ] , en[ x ] , child_sum[ x ] - down[ x ] ) ;
// }
for ( auto foo : ending_at[ x ] ) {
add_elem ( x , x ) ;
}
}
void dfs_out ( int x , int prv ) {
int wh = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_out ( y , x ) ;
if ( s[ wh ].size ( ) < s[ y ].size ( ) ) { wh = y ; }
}
swap ( s[ wh ] , s[ x ] ) ;
hh[ x ] = hh[ wh ] ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto [ pos , val ] : s[ y ] ) {
add_elem ( x , val ) ;
}
}
for ( auto id : ending_at[ x ] ) {
int y = a[ id ].fi + a[ id ].se - x ;
add_elem ( x , y ) ;
}
for ( auto id : at_lca[ x ] ) {
if ( a[ id ].fi != x ) { rem_elem ( x , a[ id ].se ) ; }
if ( a[ id ].se != x ) { rem_elem ( x , a[ id ].fi ) ; }
}
/**
printf ( "AT VERTEX %d\n" , x ) ;
for ( auto [ pos , val ] : s[ x ] ) {
printf ( "%d " , val ) ;
}
printf ( "\n" ) ;
**/
up[ x ] = n - subtree[ x ] ;
if ( s[ x ].empty ( ) == false ) {
add_elem ( x , x ) ;
int tot_lca = get_lca ( (s[ x ].begin ( ))->se , (s[ x ].rbegin ( ))->se ) ;
up[ x ] += hh[ x ] / 2 + child_sum[ tot_lca ] - child_sum[ x ] ;
// printf ( "%lld %lld %lld up = %lld\n" , hh[ x ] , child_sum[ tot_lca ] , child_sum[ x ] , up[ x ] ) ;
rem_elem ( x , x ) ;
}
}
int mxup[ MAXN ] ;
void mrk ( int x , int prv ) {
int wh = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
mrk ( y , x ) ;
if ( s[ y ].size ( ) > s[ wh ].size ( ) ) { wh = y ; }
}
swap ( s[ x ] , s[ wh ] ) ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto foo : s[ y ] ) {
s[ x ].insert ( foo ) ;
}
}
for ( auto id : ending_at[ x ] ) {
int aux = get_lca ( a[ id ].fi , a[ id ].se ) ;
s[ x ].insert ( { lvl[ aux ] , aux } ) ;
}
for ( auto id : at_lca[ x ] ) {
auto it = s[ x ].find ( { lvl[ x ] , x } ) ;
s[ x ].erase ( it ) ;
}
if ( s[ x ].empty ( ) == true ) { mxup[ x ] = LCA[ x ][ 0 ] ; }
else { mxup[ x ] = (s[ x ].begin ( ))->se ; }
if ( mxup[ x ] == 0 ) { mxup[ x ] = x ; }
}
void dfs_up ( int x , int prv ) {
if ( mxup[ x ] != 1 ) {
up[ x ] += up[ mxup[ x ] ] ; // - ( subtree[ mxup[ x ] ] - subtree[ x ] ) ;
}
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_up ( y , x ) ;
}
}
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 ) ;
}
init ( 1 , -1 ) ;
cin >> m ;
for ( int i = 1 ; i <= m ; ++ i ) {
cin >> a[ i ].fi >> a[ i ].se ;
int aux = get_lca ( a[ i ].fi , a[ i ].se ) ;
if ( a[ i ].fi != aux ) { ending_at[ a[ i ].fi ].push_back ( i ) ; }
if ( a[ i ].se != aux ) { ending_at[ a[ i ].se ].push_back ( i ) ; }
at_lca[ get_lca ( a[ i ].fi , a[ i ].se ) ].push_back ( i ) ;
}
w.init ( 1 , 1 , n ) ;
dfs_down ( 1 , -1 ) ;
/**
for ( int i = 1 ; i <= n ; ++ i ) {
printf ( "down[ %d ] = %lld\n" , i , down[ i ] ) ;
}
**/
for ( int i = 1 ; i <= n ; ++ i ) {
s[ i ].clear ( ) ;
hh[ i ] = 0 ;
}
dfs_out ( 1 , -1 ) ;
/**
for ( int i = 1 ; i <= n ; ++ i ) {
printf ( "up[ %d ] = %lld\n" , i , up[ i ] ) ;
}
**/
for ( int i = 1 ; i <= n ; ++ i ) {
s[ i ].clear ( ) ;
hh[ i ] = 0 ;
}
mrk ( 1 , -1 ) ;
dfs_up ( 1 , -1 ) ;
assert ( up[ 1 ] == 0 ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
cout << up[ i ] + child_sum[ i ] << " " ;
}
cout << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 35468kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 7 7
result:
ok single line: '6 9 9 10 7 7 '
Test #2:
score: 0
Accepted
time: 2ms
memory: 37296kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Runtime Error
input:
16384 9137 490 3442 7239 1621 6904 13769 10250 14672 12572 14906 9437 6163 12339 15244 12016 3022 8670 3211 9106 11966 14817 15798 15876 6423 7394 894 7695 13877 1983 16342 15158 13574 15932 15125 10722 6989 15683 10335 8801 12301 4246 6166 3893 9347 12073 7897 12195 6510 3101 4526 15385 7017 7001 4...