https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting link-cut tree で解けるということは知っていたので、link-cut tree で解法を考えてみた。 euler tour を用いた解法はこちら。 pekempey.hatenablog.com

問題 n 頂点のグラフがある。各頂点 i に対して、 i から a[i] に辺を張る i から n に辺を張る のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0 と 1 が連結であるようなものの個数を求めよ。 1≦n≦50

問題 k の約数ではない 2 番目に小さい正の整数を S(k) とする。S(1)+S(2)+...+S(n) を求めよ。 1≦n≦109

問題 n 頂点のグラフがある。各頂点 i に対して、 i から a[i] に辺を張る i から n に辺を張る のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0..n-1 が連結であるようなものの個数を求めよ。 1≦n≦50