AtCoder ABC282
またも3完。2回連続5完は夢だったのか？
B問題で凡ミスしてC問題ACまで13分。
- 二部グラフでググって、Union-Findを使った実装を取ってくる
- 木のルートとサイズのmapを作る
- mapのサイズが2なら、B*W-Mが答え。
- これでAC27、WE20
- 木のサイズを64bitに変更でAC29、WE18
- 後のWE18はassert()でチェックするに木が4より多い。どういうことだ？
解説を読んでも、木が4より多い（二部グラフが2より多い）問題で答えが0にならない理由がわからなかったが、
おそらく二部グラフA、B、Cがあって、AとBをつなぎ、AB、Cという状態でも問題の条件が満たされる。
ちなみに、解説にある式で二部グラフが1つの場合
N(N-1)/2 - B(B-1)/2 - W(W-1)/2 - M
は、上記のB*W-Mと一致する（W=N-Bなので）。
しかし二部グラフが1より多い場合に計算するなら、解説の方の式でないと式を求めることが非常に困難。
- i, jに対するA_i^A_j+A_j^A_i (mod M)はatcoder/modintを用いてあらかじめtable[509][509]に求めておく。
- その中から、条件を満たしつつ和が最大になるようにN-1個を選ぶ。
2の条件を満たしつつの部分を全探索すると500!でもちろん間に合わない。
DPかと思ったが、解説を読むと最大全域木だった。
