题意：初始时给出一个图，每个点有一个权值,三种操作：（1）删除某个边；（2）修改每个点的权值；（3）询问与节点x在一个连通分量中所有点的第K大的权值。
思路：反着做。删边变为加边，然后就好做了。
（1）增加某个边，用并查集找到这两个点的根节点，没在一起则合并；合并的时候为了能维护treap的性质，只能将某个树的节点一个一个插到另一个树上。这里我选择节点少的那个插到节点多的那个上显然是最优的；
（2）修改权值，将原来的权值删掉，插入新的权值；
（3）查找就是简单的select。
const int N=10000005;
int L[N],R[N],Key[N],Pri[N],s[N];
int size;
int root[N];
void pushUp(int x)
{
if(x==-1) return;
s[x]=1;
if(L[x]!=-1) s[x]+=s[L[x]];
if(R[x]!=-1) s[x]+=s[R[x]];
}
void rotL(int &x)
{
int y=R[x];
R[x]=L[y]; pushUp(x);
L[y]=x; pushUp(y);
x=y;
}
void rotR(int &x)
{
int y=L[x];
L[x]=R[y]; pushUp(x);
R[y]=x; pushUp(y);
x=y;
}
void insert(int &k,int key)
{
if(k==-1)
{
k=++size;
s[k]=1;
L[k]=R[k]=-1;
Key[k]=key;
Pri[k]=rand();
}
else if(key<Key[k])
{
s[k]++;
insert(L[k],key);
if(Pri[L[k]]>Pri[k]) rotR(k);
}
else
{
s[k]++;
insert(R[k],key);
if(Pri[R[k]]>Pri[k]) rotL(k);
}
}
void remove(int &k,int key)
{
if(k==-1) return;
else if(key<Key[k]) remove(L[k],key);
else if(key>Key[k]) remove(R[k],key);
else
{
if(L[k]==-1&&R[k]==-1) k=-1;
else if(L[k]==-1) k=R[k];
else if(R[k]==-1) k=L[k];
else
{
if(Pri[L[k]]<Pri[R[k]])
{
rotL(k);
remove(L[k],key);
}
else
{
rotR(k);
remove(R[k],key);
}
}
}
pushUp(k);
}
void split(int k,int &a)
{
if(k==-1) return;
split(L[k],a);
insert(a,Key[k]);
split(R[k],a);
}
int selectK(int root,int k)
{
if(k>s[root]) return 0;
k=s[root]+1-k;
int x=root,y;
while(x!=-1)
{
y=L[x]==-1?0:s[L[x]];
if(y>=k) x=L[x];
else if(y+1>=k) return Key[x];
else k-=y+1,x=R[x];
}
return 0;
}
const int M=200005;
int n,m,u[M*3],v[M*3],w[M*3];
struct cmd
{
char op;
int x,y;
cmd(){}
cmd(char _op,int _x,int _y)
{
op=_op;
x=_x;
y=_y;
}
cmd(char _op,int _x)
{
x=_x;
op=_op;
}
};
cmd V[M*10];
int Vnum;
int F[N];
int get(int x)
{
if(F[x]!=x) F[x]=get(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=get(x);
y=get(y);
if(x==y) return;
if(s[root[x]]>=s[root[y]])
{
F[y]=x;
split(root[y],root[x]);
}
else
{
F[x]=y;
split(root[x],root[y]);
}
}
int isDel[M*3];
void build()
{
srand(time(0)); size=0; clr(s,0);
int i,x,y;
FOR1(i,n)
{
root[i]=-1;
F[i]=i;
insert(root[i],w[i]);
}
FOR1(i,m) if(!isDel[i]) Union(u[i],v[i]);
}
void deal()
{
int cnt=0,i,y;
double ans=0;
cmd p;
FORL0(i,Vnum-1)
{
p=V[i];
if(p.op=='Q')
{
cnt++; y=get(p.x);
ans+=selectK(root[y],p.y);
}
else if(p.op=='C')
{
y=get(p.x);
remove(root[y],w[p.x]);
w[p.x]=p.y;
insert(root[y],w[p.x]);
}
else Union(u[p.x],v[p.x]);
}
printf("%.6lf\n",ans/cnt);
}
int main()
{
int num=0;
Rush(n)
{
RD(m);
if(n==0&&m==0) break;
int i;
FOR1(i,n) RD(w[i]);
FOR1(i,m) RD(u[i],v[i]);
char str[10];
int x,y;
clr(isDel,0); Vnum=0;
while(1)
{
RD(str);
if(str[0]=='Q') RD(x,y),V[Vnum++]=cmd(str[0],x,y);
else if(str[0]=='D') RD(x),V[Vnum++]=cmd(str[0],x),isDel[x]=1;
else if(str[0]=='C')
{
RD(x,y);
V[Vnum++]=cmd(str[0],x,w[x]);
w[x]=y;
}
else break;
}
printf("Case %d: ",++num);
build(); deal();
}
return 0;
}