收获： \(cdq\) 分治时不要使用 \(sort\) ，尽量在求值后合并两段，从而时时间更优。 （ $ 61 $ 至 $ 70 $ 行 ）
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N = 2e5 + 1111 ;
ll n , DFN ;
struct node {
ll red , blue , dfn , siz , id ;
ll dfnto ;
}a [ N ] ;
ll h [ N ] , nt [ N << 1 ] , to [ N << 1 ] , cnt ;
inline void add ( ll x , ll y ) { nt [ ++ cnt ] = h [ x ] ; h [ x ] = cnt ; to [ cnt ] = y ; }
inline void link ( ll x , ll y ) { add ( x , y ) ; add ( y , x ) ; return ; }
inline void dfs_dfn ( ll x , ll fa ) {
a [ x ] . siz = 1 ;
a [ x ] . dfn = ++ DFN ;
for ( ll i = h [ x ] , y ; i ; i = nt [ i ] ) {
if ( ( y = to [ i ] ) == fa ) continue;
dfs_dfn ( y , x ) ;
a [ x ] . siz += a [ y ] . siz ;
}
a [ x ] . dfnto = DFN ;
}
inline bool compred ( node x , node y )
{
return x . red == y . red ?
x . blue == y . blue ?x . dfn > y . dfn : x . blue < y . blue
:
x . red < y . red ;
}
inline bool compblue ( node x , node y )
{
return x . blue == y . blue ?
x . dfnto < y . dfnto
:
x . blue < y . blue;
}
struct szsz {
ll c [ N + 111 ] ;
int lb (int x){ return x & ( - x ) ; }
int add(int x , int y) {for ( ; x <= n ; x += lb ( x ) ) c [ x ] += y ; }
int ask(int x){int rhs = 0; for( ; x ; x -= lb ( x ) ) rhs += c [ x ]; return rhs;}
} tree ;
#define mid ( ( l + r ) >> 1 )
ll ans ;
ll num [ N ] ;
node tmp [ N ] ;
ll rhs ;
inline void cdq ( int l , int r ) {
if ( l == r ) return ;
cdq ( l , mid ) ;cdq ( mid + 1 , r ) ;
int now = l ;
for ( int i = mid + 1 ; i <= r ; i ++ ) {
while ( a [ now ] . blue <= a [ i ] . blue && now <= mid )
{ tree . add ( a [ now ] . dfn , 1 ) ; now ++ ; }
num [ a [ i ] . id ] += tree . ask ( a [ i ] . dfnto ) - tree . ask ( a [ i ] . dfn - 1 ) ;
}
for ( int i = l ; i < now ; i ++ )
tree . add ( a [ i ] . dfn , -1 ) ;
rhs = 0 ;
int i = l , j = mid + 1;
while ( i <= mid && j <= r ) {
if ( compblue ( a [ i ] , a [ j ] ) ) tmp [ ++ rhs ] = a [ i ++ ];
else tmp [ ++ rhs ] = a [ j ++ ] ;
}
while ( i <= mid ) tmp [ ++ rhs ] = a [ i ++ ] ;
while ( j <= r ) tmp [ ++ rhs ] = a [ j ++ ] ;
i = l , j = 1 ;
while ( i <= r ) { a [ i ] = tmp [ j ] ; i ++ ; j ++ ; }
return ;
}
int main ( ){
cin >> n ;
for ( ll i = 1 ; i < n ; i ++ ) {
ll x , y ;
scanf ( "%d %d" , & x , & y ) ;
link ( x , y ) ;
}
// cout << '\n' << '\n' ;
for ( ll i = 1 ; i <= n ; i ++ ){
cin >> a [ i ] . red >> a [ i ] . blue ;
a [ i ] . id = i ;
}
dfs_dfn ( 1 , 0 ) ;
sort ( a + 1 , a + n + 1 , compred ) ;
cdq ( 1 , n ) ;
// cout << ans << '\n' ;
for ( int i = 1 ; i <= n ; i ++ )
if ( num [ i ] ) cout << num [ i ] << '\n' ;
return 0 ;
}