ABC 401-500/ABC409E - Pair Annihilation - 競技プログラミング用 知識集積所【6/8更新】

---

問題

ABC409E

必要知識

B以下レベルの内容は省略

• 隣接リスト（未作成）
• 深さ優先探索（未作成）

考え方

頂点Aと頂点Bにある電荷を相殺する場合、頂点Aから頂点Bまでの最短経路上のどの頂点で相殺してもコストは変わらない。
したがって、この木を根つき木と考えて、葉から順に全てを根の方向に送り出しながら相殺していく方針で解ける。
すなわち、木の深さ優先探索（未作成）をすればよい。

解答例

解答例

注意点

long long型を使う

コストが最大10000、1マスの電荷が最大10000なので、そういうのが22マス結託するとint型からあふれることがある。
もちろん、結果もあっさりあふれる。

別解