NachiaVivias

> これ $1\leq N$ のつもりだったりしますか？（0/1 や 1/0 が出力に来るし） （ $N=0$ のときは問答無用で 0/1, 1/0 を出力、これは例外なので許される、みたいなことを考えていたかもしれませんが、） 実際は $1\leq N$ にするのがよいと思います。失礼しました。

I have 2 questions : (1) Is " $|c_i| \le 10,000$ " necessary? #843 has been posted, where $N,M \leq 3000$ is preferred. How about $N,M \leq 3000$ and $|c_i|...

この問題では木の根は関係ないので各辺の両端の点を与えるのがよいと思いますが、そうすると「動的木の場合の元ネタ」がそうであるように、順列 p を与える必要が皆無だと思います。 p 無くしませんか？

むしろ問題の綺麗さだったら余計な順列を挟まないほうが察しやすくてよいと思いますが。 オンラインクエリを意識して作ったからそっちのほうが自然だ、という意味だったら、それもありだと思います

とりあえずは sparse 仕様ではないほうが良いと思います。 （需要が多そうな、全要素持つものの verify が不便になって辛そうなので）

作業中です

必要な演算について、 - Fortune の方法で √ 付きの有理数の大小比較（程度のヤバい比較）を避ける方法は分かりません（見つかりません）でした。そういう比較があるという言及がある[スライド（最後のページ）](https://www.cs.jhu.edu/~misha/Spring20/11a.pdf)はありました。 - 分割統治のほうは「点 D は △ABC の外接円の内部にあるか？」が一番難しくて、 [Wikipedia](https://en.wikipedia.org/wiki/Delaunay_triangulation) に載っている行列式で計算できるようです。（ $0 \leq x _ i,y _ i \leq X$ なら絶対値 $6 X^4$ 以下の 2 整数の大小比較で判定できる）

> Problem ID: euclideanmst docs/style.md によると `euclidean_mst` です。

作ります

注意：(cf. Range Set Range Composite https://github.com/yosupo06/library-checker-problems/pull/1085) 更新区間の選び方が一様ランダムだと、十分な回数の更新後のデータ構造のサイズが期待的にかなり小さくなります。