問題概要
頂点からなる重み付きの木が与えられる．辺の情報は 3 つの配列
によって与えられ，
番の辺は 2 頂点
間を結び，その重みは
である．また，
を，2 頂点
間の単純道のコストとする．
今，以下のようなクエリが 回くるので，処理せよ．
番の辺の重みを
に変更する
- その後，ランダムに異なる三点
を選んだとき，
を答える
解法
まず，3 点を選んだ状態を思い浮かべてみると，ある辺が選ばれた 3 点によって張られる 3 本のパスに含まれる回数は，0 または 2 であることが分かります．従って，各辺がパスに含まれる確率が分かっていれば，その確率と辺重みの積の総和を計算することで全体の期待値を求めることができます（期待値の線形性より）．また，ある辺がパスに含まれる確率は，その辺を取り除いたときにできる二つの部分グラフの頂点数から計算することができます．それぞれの部分グラフの頂点数を とします．このとき，3 点とも
側の部分グラフから選ばれる確率を
とすると，
であり，同様に，3 点とも
側の頂点から選ばれる確率を
とすれば，
となります．着目している辺がパスに含まれる場合というのは，1 つ以上のパスがその辺を含む場合であり，両方の部分グラフから 1 点以上ずつ選ばれている場合です．これは，先程上げた二つの場合の余事象なので，その確率は
となります．辺によって分断される部分グラフの頂点数は，木を適当に有向化して根付き木と考え，辺の端点の内葉に近い方を根とする部分木の頂点数を
，それ以外を
とすることで計算できます．部分木の大きさは DFS をすることで
時間で全て求められるので，各辺が使われる確率も
時間で計算できます．
さて，これでクエリが来る前の状態での期待値は求められるようになりましたが，重みの変更を効率的に処理できなければ TLE します．制約からして，クエリあたり 時間程度で処理できる必要がありそうです．
若干唐突ですが，期待値というのは実数の和なので結合律が成り立ちます．また，辺の情報を，期待値の列（実際には重みの列と確率の列の組）に直したとすると，辺へのクエリは列に対するクエリとして処理することができるようになります．これらを踏まえると，重みの更新と期待値の計算をセグメント木を使って高速化できるような気分になるのでそのようにします．
セグメント木の中身ですが，各節点には対応する区間全体の期待値を保持させます．また，葉となる頂点には，対応する辺の重みとパスに含まれる確率をもたせ，葉ノードの期待値を計算できるようにしておきます．クエリが来たとき，更新が必要になる節点は，更新された 1 点を含む区間を受け持つ節点のみなので， 時間で更新できます．更新の完了後，根に格納されている期待値がクエリの答えとして出力すべき期待値です．
コード
using LL = long long; using VI = vector< int >; template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define EB emplace_back struct Edge { int to, cost, index; double p = 0; bool used = false; Edge( const int t, const int c, const int i ) : to( t ), cost( c ), index( i ) { return; } }; int N; VVT< Edge > G; VI as; VT< double > ps; int dfs( const int v = 0, const int prev = -1 ) { int res = 1; FOR( e, G[v] ) { if ( e.to == prev ) { continue; } const LL a = dfs( e.to, v ); const LL b = N - a; const double p = 1. * a * ( a - 1 ) * ( a - 2 ) / ( LL( N ) * ( N - 1 ) * ( N - 2 ) ); const double q = 1. * b * ( b - 1 ) * ( b - 2 ) / ( LL( N ) * ( N - 1 ) * ( N - 2 ) ); as[ e.index ] = e.cost; ps[ e.index ] = 1. - p - q; res += a; } return res; } // セグメント木のユーティリティ inline int chl( const int k ) { return k * 2 + 1; } inline int chr( const int k ) { return k * 2 + 2; } inline int mid( const int l, const int r ) { return ( l + r ) / 2; } namespace SegmentTree { template < typename T > class ExpectedValueArray { private: const int N; std::vector< T > array; std::vector< double > probs, expects; public: ExpectedValueArray( const int n ) : N( n ), array( N ), probs( N ), expects( N * 4 ) { return; } ExpectedValueArray( const std::vector< T > &as, const std::vector< double > &ps ) : N( as.size() ), array( as ), probs( ps ), expects( N * 4 ) { for ( int i = 0; i < N; ++i ) { update( i, 0, 0, N ); } return; } void update_array( const int p, const int x ) { array[p] = x; update( p, 0, 0, N ); return; } void update_prob( const int p, const double x ) { probs[p] = x; update( p, 0, 0, N ); return; } double expected_value() const { return expects[0]; } private: void update( const int p, const int k, const int l, const int r ) { if ( p < l || r <= p ) { return; } if ( l + 1 == r && p == l ) { expects[k] = array[p] * probs[p]; return; } update( p, chl( k ), l, mid( l, r ) ); update( p, chr( k ), mid( l, r ), r ); expects[k] = expects[ chl( k ) ] + expects[ chr( k ) ]; return; } }; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); // cin >> N; scanf( "%d", &N ); G.resize( N ); REP( i, 0, N - 1 ) { int u, v, l; // cin >> u >> v >> l; scanf( "%d%d%d", &u, &v, &l ); --u, --v; G[u].EB( v, l, i ); G[v].EB( u, l, i ); } as.resize( N - 1 ); ps.resize( N - 1 ); dfs(); int Q; // cin >> Q; scanf( "%d", &Q ); // cout << setprecision( 8 ) << fixed; SegmentTree:: ExpectedValueArray< int > segtree( as, ps ); REP( iteration, 0, Q ) { int r, w; // cin >> r >> w; scanf( "%d%d", &r, &w ); --r; segtree.update_array( r, w ); // cout << segtree.expected_value() * 2 << '\n'; printf( "%.8lf\n", segtree.expected_value() * 2 ); } // cout << flush; fflush( stdout ); return 0; }
