感觉做得有点复杂了，但是AC了还是。。。爽。。。
题意：给你n个点每个点有一个价值，接下来有m条边，然后是q个操作，每个操作有三种情况：
F X K：寻找与X点直接或间接相连的不小于价值K的最小价值，如果找不到就是0
U X K：将X点价值变为K
E A B：删除点A与点B形成的边
最后求价值总和的平均值
首先我们看F操作和U操作可以使用map解决，因为这是典型的带修改并区间找寻大于等于某值的最小值。然后我们看删边，如果直接删的话，我们需要遍历这一维map然后拆分，时间过不了。因此我们想到使用离线操作倒序添边，然后处理集合合并问题就是并查集的典型题了。
接着我们离线后要把每个E与U都处理后再添边，对于U我们必须保存所有修改的历史，因此使用vector。而m条边中删除E的边，我们需要节约时间。存下总所有边与需要删除的边，然后一起排序后双指针维护添边（因为需要删除的边一定在所有边中出现过，且没有重边）。接着对于维护E，添边后需要把一个父节点并上去，且两个map也要合并，因此我们为了节约合并时间，需要简单的启发式合并。其实就是并查集合并时把个数少的并到个数多的上面。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
struct node
{
char typ[];
int u,v;
}add[Max],del[Max],ope[Max];
int fat[Max],ran[Max];//离线添边的并查集
map<int,int> mp[Max];//祖先形成的集合里的元素
vector<int> vec[Max];//存下修改的过程值
int len[Max];
void Init(int n)
{
for(int i=;i<n;++i)
{
ran[i]=;
len[i]=;
vec[i].clear();
mp[i].clear();
fat[i]=i;
}
return;
}
int Find(int x)
{
if(x==fat[x])
return fat[x];
return fat[x]=Find(fat[x]);
}
void UnMap(int x1,int y1)
{
for(map<int,int>::iterator it=mp[x1].begin();it!=mp[x1].end();)
{
if(!mp[y1].count(it->first))
mp[y1][it->first]=it->second;
else
mp[y1][it->first]+=it->second;
mp[x1].erase(it++);//删除
}
return;
}
void Union(int x,int y)
{
int x1=Find(x);
int y1=Find(y);
if(x1==y1)
return;
if(ran[x1]<ran[y1])
{
fat[x1]=y1;//价值合并
ran[y1]+=ran[x1];
UnMap(x1,y1);
}
else
{
fat[y1]=x1;//价值合并
ran[x1]+=ran[y1];
UnMap(y1,x1);
}
return;
}
bool cmp(struct node p1,struct node p2)
{
if(p1.u==p2.u)
return p1.v<p2.v;
return p1.u<p2.u;
}
map<int,int>::iterator it;
double Solve(int n,int m,int q,int cnt,int dig)
{
int coun=;
double ans=0.0;
for(int i=;i<n;++i)
mp[i][vec[i][len[i]]]=;//开始每个集合是自己
sort(add,add+m,cmp);
sort(del,del+cnt,cmp);
del[cnt].u=del[cnt].v=-;
//for(int i=0;i<m;++i)
// printf("%d %d\n",add[i].u,add[i].v);
// printf("OK\n");
// for(int i=0;i<cnt;++i)
//printf("%d %d\n",del[i].u,del[i].v);
for(int i=;i<m;++i)//初始添边
{
if(add[i].u==del[coun].u&&add[i].v==del[coun].v)//两边排序后双指针维护
coun++;
else
{//printf("OK\n");
Union(add[i].u,add[i].v);
}
}
for(int i=q-;i>=;--i)
{
if(ope[i].typ[]=='F')
{
int x1=Find(ope[i].u);
it=mp[x1].lower_bound(ope[i].v);
if(it==mp[x1].end())
ans+=0.0;
else
ans+=it->first;
}
else if(ope[i].typ[]=='E')
Union(ope[i].u,ope[i].v);
else//换价值
{
int x1=Find(ope[i].u);
mp[x1][ope[i].v]--;
if(mp[x1][ope[i].v]==)
mp[x1].erase(ope[i].v);
if(mp[x1].count(vec[ope[i].u][len[ope[i].u]-]))
mp[x1][vec[ope[i].u][--len[ope[i].u]]]++;
else
mp[x1][vec[ope[i].u][--len[ope[i].u]]]=;
}
}//printf("%d\n",dig);
return ans/dig;
}
int main()
{
int n,m,q;
int u,v,c;
int cnt,dig,coun=;
while(~scanf("%d %d %d",&n,&m,&q))
{
Init(n);
dig=cnt=;
for(int i=;i<n;++i)
{
scanf("%d",&c);
vec[i].push_back(c);
}
for(int i=;i<m;++i)
{
scanf("%d %d",&u,&v);
u--,v--;
if(u>v)
swap(u,v);
add[i].u=u;
add[i].v=v;
}
for(int i=;i<q;++i)
{
scanf("%s %d %d",&ope[i].typ,&ope[i].u,&ope[i].v);
if(ope[i].typ[]=='F')
{
dig++;
ope[i].u--;
}
else if(ope[i].typ[]=='E')
{
ope[i].u--,ope[i].v--;
if(ope[i].u>ope[i].v)
swap(ope[i].u,ope[i].v);
del[cnt].u=ope[i].u,del[cnt++].v=ope[i].v;
}
else
{
ope[i].u--;
len[ope[i].u]++;
vec[ope[i].u].push_back(ope[i].v);
}
}
printf("Case %d: %.3f\n",++coun,Solve(n,m,q,cnt,dig));
Init(n);
}
return ;
}