CFR 740 D. Alyona and a tree ( Monotonicity )

題意：
給一棵樹，有點權和邊權。定義 f( v, u ) 為真，若 u 為 v 的子樹裡的節點，且 dis( u, v ) ≤ 邊權[ u ]。對樹上所有節點 x，求 SIGMA( f( x, y ) | ALL y )。

資料規模：
節點數 1 ≤ n ≤ 2e5
點權 1 ≤ a[ i ]≤ 1e9
邊權 1 ≤ w[ i ]≤ 1e9
時限 2000 ms
記憶體 256 MB

解法：
先將 0 提為根，轉為有根樹。
由於 u 為 v 的子樹裡的節點，定義 d( x ) 為 x 至根的距離，那麼原不等式改寫成 d( u ) - d( v ) ≤ a( u ) -> d( u ) - a( u ) ≤ d( v )。因此每個 u 對每個祖先 v 都有一個貢獻，若且唯若該不等式滿足。如果按照 dfs 的順序處理，那只關心的是來自根的那條鏈。又注意到鏈越淺的位置的祖先 v，其 d( v ) 有越小的單調性，因此考慮類似子鏈前綴和的概念做貢獻的更新。方法就是預設當前的點會對所有祖先造成貢獻，貢獻會一直往上保留，但又因為可能某個祖先 v 以上的點都不能享受這些貢獻，便要在該祖先 v 的貢獻前綴和值 -1 補回來。

時間 / 空間複雜度：
O( N lg N ) / O( N )

int N;
vi A;
vvp G;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    G = vvp( N );
    for( int i = 1; i < N; ++i ){
        int P, W; cin >> P >> W;
        G[ P - 1 ].emplace_back( W, i );
    }
}

vi ans;

void dfs( int u, int fa, ll d, vector< pair< ll, int > > &chain ){ // dis( u, v ) ≤ a( u ) -> d( u ) - d( v ) ≤ a( u ) -> d( u ) - a( u ) ≤ d( v ) -> ++ans[ v ]
    ++ans[ u ];
    auto it = lower_bound( chain.begin(), chain.end(), make_pair( d - A[ u ], -1 ) );
    if( it-- != chain.begin() )
        --ans[ it->second ];
    chain.emplace_back( d, u );
    for( int i = 0; i < G[ u ].size(); ++i ){
        int w, v; tie( w, v ) = G[ u ][ i ];
        if( v == fa ) continue;
        dfs( v, u, d + w, chain );
        ans[ u ] += ans[ v ];
    }
    chain.pop_back();
}

void preprocess(){
    ans = vi( N );
    vector< pair< ll, int > > _chain; dfs( 0, -1, 0, _chain );
}

void solve(){
    for( int i = 0; i < N; ++i )
        cout << ans[ i ] - 1 << " \n"[ i + 1 == N ];
}