\(xy\) 平面上に \(N\) 個の頂点からなる木があります。頂点には \(1,2,\ldots,N\) の番号が付いており、頂点 \(i\) の座標は \((x_i,y_i)\) です。
木の \(j\) 番目の辺は頂点 \(u_j\) と頂点 \(v_j\) を結んでいます。この辺の長さは、\(2\) 頂点間のユークリッド距離 \(\sqrt{(x_{u_j}-x_{v_j})^2+(y_{u_j}-y_{v_j})^2}\) です。
\(Q\) 個のクエリが与えられます。\(q\) 番目のクエリでは、既存の辺とは別に、頂点 \(W_q\) と頂点 \(X_q\) を結ぶ辺を \(1\) 本追加します。追加する辺の長さも \(2\) 頂点間のユークリッド距離です。\(W_q=X_q\) の場合、追加する辺の長さは \(0\) です。
頂点 \(1\) から出発し、辺を通ってすべての頂点を少なくとも \(1\) 回訪れたあと、頂点 \(1\) に戻ることを考えます。それぞれの辺は、どちらの向きにも何度でも通ることができます。このような移動で通る辺の長さの総和としてありうる最小値を求めてください。
各クエリは独立です。あるクエリで追加した辺は、それ以降のクエリには残りません。
入力は以下の形式で標準入力から与えられます。
| \(N\) | |
| \(x_1~y_1\) | |
| \(x_2~y_2\) | |
| \(\vdots\) | |
| \(x_N~y_N\) | |
| \(u_1~v_1\) | |
| \(u_2~v_2\) | |
| \(\vdots\) | |
| \(u_{N-1}~v_{N-1}\) | |
| \(Q\) | |
| \(W_1~X_1\) | |
| \(W_2~X_2\) | |
| \(\vdots\) | |
| \(W_Q~X_Q\) |
制約は以下の通りです。
\(Q\) 行出力してください。
\(q\) 行目には、\(q\) 番目のクエリで辺を追加したときに必要な距離の最小値を出力してください。
想定解との絶対誤差または相対誤差が \(10^{-6}\) 以下であれば正解と判定されます。
30 03 03 41 22 331 31 22 2
12.000000000000000 14.000000000000000 14.000000000000000
40 00 34 30 71 22 32 433 41 31 4
19.656854249492380 20.000000000000000 22.000000000000000
サンプル1について:
はじめの木の辺の長さの総和は \(3+4=7\) です。
\(1\) 番目のクエリでは、頂点 \(1\) と頂点 \(3\) を結ぶ長さ \(5\) の辺を追加します。頂点 \(1,2,3,1\) の順に移動すると、移動距離は \(3+4+5=12\) になります。
\(2\) 番目のクエリで追加する辺は、もとの辺と同じ長さです。どちらか一方の辺を使って頂点 \(2\) へ行き、もう一方の辺を使って頂点 \(1\) へ戻ることができます。
\(3\) 番目のクエリで追加する辺の長さは \(0\) です。この辺を追加しても最小値は変わりません。
サンプル2について:
\(1\) 番目のクエリでは、頂点 \(3\) と頂点 \(4\) を結ぶ長さ \(\sqrt{32}\) の辺を追加します。例えば頂点 \(1,2,3,4,2,1\) の順に移動するのが最適です。