Description：

$n$ 个点 $m$ 条边的无向图，每个点的纪念品有一个价格，执行 $q$ 次操作：

1、改变一个点的纪念品价格。

2、询问 $x$ 到 $y$ 任意简单路径上最便宜的纪念品。

$1\le n,m,q \le 10^5$

Solution：

不难想到将每个点双联通分量缩点再用树链剖分维护。但是发现一个割点可能属于多个点双连通分量，如果在每个里面都维护的话会被菊花图卡掉，于是对于每个点双连通分量新建一个节点并将这个点与点双内所有点相连，再对这棵树树链剖分，将每个点的值保存在这个点和他的父亲上，这样每个代表点双的点都维护了该点双内除最高割点以外的点的值，对于询问，发现如果 $LCA$ 是一个代表点双的点，那么这个点双的最高点没有被计算，于是特判即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<stack>

#include<vector>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 100010

vector<int> g[MAXN];

int w[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 3];

int edgenum = 0;

int lin[MAXN << 1] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool cut[MAXN];

int vdcc = 0;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);

	for(int i = 0;i < g[k].size();++i)

		if(dfn[g[k][i]] == 0)

		{

			tarjan(g[k][i]);

			low[k] = min(low[k],low[g[k][i]]);

			if(low[g[k][i]] >= dfn[k])

			{

				cut[k] = true;

				++vdcc;

				int p;

				do

				{

					p = s.top();s.pop();

					add(vdcc,p);

				}while(p != g[k][i]);

				add(vdcc,k);

			}

		}

		else

			low[k] = min(low[k],dfn[g[k][i]]);

	return;

}

int dep[MAXN << 1],top[MAXN << 1],siz[MAXN << 1],son[MAXN << 1],fa[MAXN << 1],rank[MAXN << 1],th[MAXN << 1],cnt = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rank[k] = ++cnt;

	th[cnt] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

#define mid ((l + r) >> 1)

struct node

{

	multiset<int> s;

	int lc,rc,minv;

	node(){minv = 0x3f3f3f3f;s.insert(0x3f3f3f3f);}

}t[MAXN << 2];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].minv = 0x3f3f3f3f;

	if(l == r)

		return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int p,int v,int l,int r)

{

	if(l == r)

	{

		t[rt].s.insert(v);

		t[rt].minv = (*t[rt].s.begin());

		return;

	}

	if(p <= mid)add(t[rt].lc,p,v,l,mid);

	else add(t[rt].rc,p,v,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

void del(int rt,int p,int v,int l,int r)

{

	if(l == r)

	{

		t[rt].s.erase(t[rt].s.find(v));

		t[rt].minv = (*t[rt].s.begin());

		return;

	}

	if(p <= mid)del(t[rt].lc,p,v,l,mid);

	else del(t[rt].rc,p,v,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].minv;

	int res = 0x3f3f3f3f;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R >= mid + 1)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

char getc()

{

	char c = getchar();

	while(c != 'A' && c != 'C')c = getchar();

	return c;

}

int query()

{

	int a,b;

	scanf("%d%d",&a,&b);

	int res = 0x3f3f3f3f;

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		res = min(res,query(root,rank[top[a]],rank[a],1,vdcc));

		a = fa[top[a]];

	}

	if(dep[a] < dep[b])swap(a,b);

	res = min(res,query(root,rank[b],rank[a],1,vdcc));

	if(fa[b] != 0 && fa[b] <= n)res = min(res,w[fa[b]]);

	return res;

}

void change()

{

	int a,b;

	scanf("%d%d",&a,&b);

	del(root,rank[a],w[a],1,vdcc);

	del(root,rank[fa[a]],w[a],1,vdcc);

	w[a] = b;

	add(root,rank[a],w[a],1,vdcc);

	add(root,rank[fa[a]],w[a],1,vdcc);

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)

		scanf("%d",&w[i]);

	vdcc = n;

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		g[a].push_back(b);g[b].push_back(a);

	}

	memset(dfn,0,sizeof(dfn));

	tarjan(1);

	dfs1(1,1);

	dfs2(1,1);

	build(root,1,vdcc);

	for(int i = 1;i <= n;++i)

	{

		add(root,rank[i],w[i],1,vdcc);

		add(root,rank[fa[i]],w[i],1,vdcc);

	}

	for(int i = 1;i <= q;++i)

		if(getc() == 'A')

			printf("%d\n",query());

		else change();

	return 0;

}