#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int LL; typedef pair P; typedef pair LP; const int INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i q1; vector parent; vector num; typedef long double D; public: vector v1; void init(){ parent.assign(n,-1); num.assign(n,1); v1.assign(n,node()); } union_find_tree(int n_init){ assert(n_init>=0); n=n_init; init(); } union_find_tree(){ n=N; init(); } int check_parent(int x){ assert(x>=0 && x=0 && x=0 && ynum[y])swap(x,y); parent[x]=y; num[y]+=num[x]; D s=-v1[x].calc()-v1[y].calc(); v1[y].connect(v1[x]); return s+v1[y].calc(); } int size(int pos){ pos=check_parent(pos); return num[pos]; } }; int main(){ int n,m; int i,j,k; int a,b,c; cin>>n; union_find_tree ua(n); for(i=0;i>ua.v1[i].a; for(i=0;i>ua.v1[i].b; for(i=0;i>ua.v1[i].p; long double s=0; for(i=0;i>m; cout<>a>>b; a--,b--; s+=ua.connect(a,b); cout<