"「ある頂点の子孫でない頂点に xを足す」は、 「根の子孫に xを足す」と「ある頂点の子孫に -xを足す」に分けることができるので、 全てのクエリを「ある頂点の子孫に x を足す」の形に帰着することができます。"かしこい。は？となりながら解説の言うとお…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…