[AtCoder] ABC 138 D – Ki

問題

方針

幅優先探索

頂点 \( 1 \) から幅優先探索を行って全ての頂点のカウンターの値を計算します。そのために、頂点 \( i \) が最初のカウンターの値をあらかじめ計算します。最初のカウンターの値とは、ある頂点 \( u \) が \( u = p_i \ (1 \leq i \leq N)\) を満たすような頂点 \( u \) に \( x_i \) を加算した値です。ここで、頂点 \( i \) のカウンターの値を \( c_i \) とします。

頂点 \( 1 \) を親として、子のカウンターの値に \( c_1 \) を加算するというように、親から子に向かってカウンターの値を加算していきます。この探索では、隣接リストとキューを用いて幅優先探索を行うことができます。

コード