Quiz
https://yukicoder.me/problems/no/416
Submit
https://yukicoder.me/submissions/339563
解法
- 破壊される辺以外を張っておく
- 破壊クエリを逆から読みながらその辺を復活させていく
- 木がつながったかはUnion Findで管理する
- 辺を繋げる前に、今回の接続で初めて「点1とつながっている木」「点1とつながっていない木」が接続されるなら、それは破壊で通れなくなった日である
- 「点1とつながっていない木」が隔離される日がわかったので、「点1とつながっていない木」のノード全てをdfsで走査して、日にちを書き込む
参考にしたもの
- 公式解法
- はむこさん
サンプル1