蒟蒻求助 TLE on #29

#include <bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f = ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

const int N = 2e5 + 5, M = 5e6 + 5, inf = 0x3f3f3f3f; 

struct Tree {
	int head[N], nex[M], ver[M], dfn[N], num, tot = 1;
	void add(int x, int y) { ver[++tot] = y; nex[tot] = head[x]; head[x] = tot; }
};
Tree tr, yf; 
int n, m, q, rt, val[N];
int low[N], cnt;  
bool cut[N];
int stk[N], tp;  
int fan[N], fa[N], siz[N], ms[N], dep[N], top[N]; 
multiset<int> dcc[N]; 

void tarjan(int x) {
	tr.dfn[x] = low[x] = ++tr.num; 
	stk[++tp] = x; 
	int flag = 0, son = 0; 
	for (int i = tr.head[x]; i; i = tr.nex[i]) {
		int y = tr.ver[i]; 
		if (!tr.dfn[y]) {
			tarjan(y); 
			low[x] = min(low[x], low[y]); 
			++son; 
			if (tr.dfn[x] <= low[y]) {
				++flag; 
				if (flag > 1 || x != rt) cut[x] = 1; 
				++cnt; 
				int z; 
				do {
					z = stk[tp--]; 
					yf.add(n + cnt, z); yf.add(z, n + cnt); 
//					dcc[cnt].emplace(val[z]); 
				} while (z != y);
				yf.add(n + cnt, x); yf.add(x, n + cnt); 
//				dcc[cnt].emplace(val[x]);  
			}
		} else low[x] = min(low[x], tr.dfn[y]); 
	}
	if (x == rt && !son) ++cnt, yf.add(n + cnt, x), yf.add(x, n + cnt); // dcc[cnt].emplace(val[x]); 
}

struct SegMentTree {
	int l, r, mi; 
};
SegMentTree nd[N << 2]; 

void update(int now) { nd[now].mi = min(nd[now << 1].mi, nd[now << 1 | 1].mi); }

void Build_tree(int now, int l, int r) {
	nd[now].l = l; nd[now].r = r; 
	if (l == r) { nd[now].mi = val[fan[l]]; return; }
	int mid = (l + r) >> 1; 
	Build_tree(now << 1, l, mid); Build_tree(now << 1 | 1, mid + 1, r); 
	update(now); 
}

void change(int now, int p, int k) {
	if (nd[now].l == nd[now].r) {
		nd[now].mi = k; 
		return; 
	}
	int mid = (nd[now].l + nd[now].r) >> 1; 
	if (p <= mid) change(now << 1, p, k); 
	else change(now << 1 | 1, p, k);
	update(now); 
}

int query(int now, int l, int r) {
	if (nd[now].l == nd[now].r) {
		return nd[now].mi; 
	}
	int mid = (nd[now].l + nd[now].r) >> 1; 
	if (r <= mid) return query(now << 1, l, r); 
	else if (l > mid) return query(now << 1 | 1, l, r);
	else return min(query(now << 1, l, mid), query(now << 1 | 1, mid + 1, r));  
}

void dfs1(int x, int father) {
	fa[x] = father; 
	siz[x] = 1; 
	dep[x] = dep[father] + 1; 
	for (int i = yf.head[x]; i; i = yf.nex[i]) {
		int y = yf.ver[i]; 
		if (y == father) continue; 
		dfs1(y, x);
		if (x > n) dcc[x - n].emplace(val[y]);  
		if (siz[y] > siz[ms[x]]) ms[x] = y; 
		siz[x] += siz[y]; 
	}
} // fa siz dep ms

void dfs2(int x, int topx) {
	top[x] = topx; 
	yf.dfn[x] = ++yf.num; 
	fan[yf.num] = x; 
	if (!ms[x]) return;
	dfs2(ms[x], topx); 
	for (int i = yf.head[x]; i; i = yf.nex[i]) {
		int y = yf.ver[i]; 
		if (y == fa[x] || y == ms[x]) continue; 
		dfs2(y, y); 
	}
}

int queryd(int x, int y) {
	int res = inf; 
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) swap(x, y); // dep[top[x]] <= dep[top[y]]
		res = min(res, query(1, yf.dfn[top[y]], yf.dfn[y])); y = fa[top[y]]; 
	}
	if (dep[x] > dep[y]) swap(x, y); // dep[x] <= dep[y].
	res = min(res, query(1, yf.dfn[x], yf.dfn[y])); 
	if (x > n) res = min(res, val[fa[x]]); 
	return res; 
}

int main() {
	n = read(); m = read(); q = read(); 
	for (int i = 1; i <= n; ++i) val[i] = read(); 
	for (int i = 1; i <= m; ++i) {
		int u = read(), v = read(); 
		tr.add(u, v); tr.add(v, u); 
	}
	for (int i = 1; i <= n; ++i) {
		if (!tr.dfn[i]) {
			rt = i; tarjan(i); 
			dfs1(i, 0); 
			dfs2(i, i); 
		}
	}
	for (int x = n + 1; x <= n + cnt; ++x) {
		val[x] = *dcc[x - n].begin(); 
	}
	Build_tree(1, 1, n + cnt); 
	while (q--) {
		char opt = getchar(); 
		while (opt < 'A' || opt > 'Z') opt = getchar(); 
		if (opt == 'C') {
			int a = read(), w = read(), f = fa[a];
			if (f) {
				dcc[f - n].erase(val[a]); 
				dcc[f - n].emplace(w); 
				val[f] = *dcc[f - n].begin(); 
				change(1, yf.dfn[f], val[f]); 
			}
			val[a] = w; 
			change(1, yf.dfn[a], w); 
		} else {
			int a = read(), b = read(); 
			printf("%d\n", queryd(a, b)); 
		}
	} 
	return 0;
}