1、感谢taorunz老师
2、题目大意：就是给个带权无向图，然后有两种操作，
1是修改某个点的权值
2是询问，询问一个值，就是u到v之间经过点权的最小值(不可以经过重复的点)
操作数，点数，边数都不超过100000
3、分析：首先看这道题，就感觉用双联通+树剖搞一搞可以过，可是怎么搞呢
首先双联通是必然的了，可是正常的缩点+树剖会爆零随便试试就知道了
然后我们需要不正常的缩点，我们在正常的缩点后加入割点，割点向它所属的一切双联通分量连边
这样，我们就不怕询问的u和v中有割点了，可是虽然询问是logn*logn了，但是修改会超时，于是我们想想应该怎么搞呢
taorunz告诉我说，图会满足一个性质，块的父亲是割点，割点的父亲是块，我们维护块的值是，
这个块所代表的双联通，除了它父亲的那个割点，那么我们这么修改，如果修改的非割点，就正常修改,
如果是割点，那么它的父亲这个块也要修改，这样修改就是o(logn)了，我们就可以过了，但是树剖的询问中
如果lca是块，我们还要询问这个块的父亲，这样，这道题就完美的AC了，（各种bug
</pre><pre name="code" class="cpp">#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
struct node{
int from, to, next;
} G[2000010];
struct segment_tree{
int q[50000010];
int x, y;
inline void init(){
for(int i = 1; i <= 4500000; i ++) q[i] = 2147483647;
return;
}
inline void add(int l, int r, int o){
if(l == r && l == x){
q[o] = y;
return;
}
int mid = (l + r) / 2;
if(x <= mid) add(l, mid, 2 * o);
if(x > mid) add(mid + 1, r, 2 * o + 1);
q[o] = q[2 * o];
if(q[2 * o + 1] < q[o]) q[o] = q[2 * o + 1];
return;
}
inline int query(int l, int r, int o){
if(x <= l && r <= y){
return q[o];
}
int mid = (l + r) / 2;
int ret = 2147483647;
if(x <= mid){
int wl = query(l, mid, 2 * o);
if(wl < ret) ret = wl;
}
if(y > mid){
int wl = query(mid + 1, r, 2 * o + 1);
if(wl < ret) ret = wl;
}
return ret;
}
} qzh, mmd;
struct tree_chain_paritition{
int Top[2000010];
int Size[2000010];
int Height[2000010];
int Father[2000010];
int Num[2000010];
int value[2000010];
node G[2000010];
int head[2000010], ff, de, n;
int vis[2000010];
int is_cut[2000010];
inline void for_tree(){
for(int i = 1; i <= n; i ++) is_cut[i] = 1;
}
inline void init(){
memset(is_cut, 0, sizeof(is_cut));
memset(head, -1, sizeof(head));
de = 0;
}
inline void insert(int u, int v){
//printf("%d %d\n", u, v);
ff ++;
G[ff] = (node){u, v, head[u]};
head[u] = ff;
return;
}
inline void dfs1(int u, int fa, int k){
Father[u] = fa;
Height[u] = k;
Size[u] = 1;
vis[u] = 1;
for(int i = head[u]; i != -1; i = G[i].next){
node e = G[i];
if(!vis[e.to]){
dfs1(e.to, u, k + 1);
Size[u] += Size[e.to];
}
}
return;
}
inline void dfs2(int u, int fa){
vis[u] = 1;
int o = 0, pos;
for(int i = head[u]; i != -1; i = G[i].next){
node e = G[i];
if(!vis[e.to]){
if(Size[e.to] > o){
pos = i;
o = Size[e.to];
}
}
}
if(o != 0){
node e = G[pos];
qzh.x = ++ de;
qzh.y = value[e.to];
qzh.add(1, n, 1);
Top[e.to] = Top[u];
Num[e.to] = de;
dfs2(e.to, u);
}
for(int i = head[u]; i != -1; i = G[i].next){
node e = G[i];
if(!vis[e.to] && i != pos){
qzh.x = ++ de;
qzh.y = value[e.to];
qzh.add(1, n, 1);
Top[e.to] = e.to;
Num[e.to] = de;
dfs2(e.to, u);
}
}
return;
}
inline void solve(){
qzh.x = ++ de;
qzh.y = value[1];
qzh.add(1, n, 1);
Top[1] = 1;
Num[1] = de;
memset(vis, 0, sizeof(vis));
dfs2(1, 0);
return;
}
inline void change(int s, int t){
qzh.x = Num[s];
qzh.y = t;
qzh.add(1, n, 1);
return;
}
inline int qmin(int s, int t){
int ret = 2147483647;
while(Top[s] != Top[t]){
if(Height[Top[s]] > Height[Top[t]]) swap(s, t);
qzh.x = Num[Top[t]];
qzh.y = Num[t];
int wl = qzh.query(1, n, 1);
if(wl < ret) ret = wl;
t = Father[Top[t]];
}
if(Height[s] > Height[t]) swap(s, t);
qzh.x = Num[s];
qzh.y = Num[t];
int wl = qzh.query(1, n, 1);
if(wl < ret) ret = wl;
if(!is_cut[s] && s != 1){
qzh.x = Num[Father[s]];
qzh.y = Num[Father[s]];
wl = qzh.query(1, n, 1);
if(wl < ret) ret = wl;
}
return ret;
}
inline void debug(){
printf("\nNum:");
for(int i = 1; i <= n; i ++) printf("%d ", Num[i]);
printf("\nSize:");
for(int i = 1; i <= n; i ++) printf("%d ", Size[i]);
printf("\nHeight:");
for(int i = 1; i <= n; i ++) printf("%d ", Height[i]);
printf("\nTop:");
for(int i = 1; i <= n; i ++) printf("%d ", Top[i]);
printf("\n");
}
} wt;
int first[2000010], Next[2000010], poss[2000010], Left[2000010], Right[2000010];
int labccno[2000010];
int ff;
int w[2000010];
int head[2000010], next[2000010];
int pre[2000010], iscut[2000010], bccno[2000010], use_times[2000010];
int head1[2000010], next1[2000010], kt[2000010];
int vis[2000010];
int dfs_clock, bcc_cnt;
int dark;
int he[2000010], ne[2000010];
int poss_fa[2000010];
stack<node> S;
inline int dfs(int u, int fa);
inline void insert(int u, int v);
int main(){
int n, m, q;
while(scanf("%d%d%d", &n, &m, &q) != EOF){
memset(head, -1, sizeof(head));
memset(first, -1, sizeof(first));
memset(head1, -1, sizeof(head1));
memset(iscut, 0, sizeof(iscut));
memset(he, -1, sizeof(he));
for(int i = 1; i <= n; i ++){
scanf("%d", &w[i]);
}
for(int i = 1; i <= m; i ++){
int u, v;
scanf("%d%d", &u, &v);
insert(u, v);
insert(v, u);
}
dfs_clock = bcc_cnt = 0;
for(int i = 1; i <= n; i ++){
if(!pre[i]) int wl = dfs(i, -1);
}
for(int i = 1; i <= n; i ++) labccno[i] = bccno[i];
/*for(int i = 1; i <= n; i ++){
printf("%d ", bccno[i]);
}
printf("\n");*/
for(int i = 1; i <= n; i ++){
if(iscut[i]){
bcc_cnt ++;
bccno[i] = bcc_cnt;
}
}
qzh.init();
wt.init();
wt.n = bcc_cnt;
for(int i = 1; i <= bcc_cnt; i ++) wt.value[i] = 2147483647;
for(int i = 1; i <= n; i ++){
wt.value[bccno[i]] = min(wt.value[bccno[i]], w[i]);
}
memset(vis, 0, sizeof(vis));
/*for(int i = 1; i <= n; i ++){
printf("%d ", bccno[i]);
}
printf("\n");*/
for(int i = 1; i <= n; i ++){
if(iscut[i]){
for(int j = head1[i]; j != -1; j = next1[j]){
wt.insert(bccno[i], kt[j]);
wt.insert(kt[j], bccno[i]);
//wt.value[kt[j]] = min(wt.value[kt[j]], w[i]);
}
}
else{
for(int j = head[i]; j != -1; j = G[j].next){
int ii = bccno[i], jj = bccno[G[j].to];
if(ii != jj){
wt.insert(ii, jj);
wt.insert(jj, ii);
}
}
}
}
memset(wt.vis, 0, sizeof(wt.vis));
wt.dfs1(1, 0, 1);
int N = n;
for(int i = 1; i <= n; i ++) if(iscut[i]){
N ++;
ne[i] = he[wt.Father[bccno[i]]];
he[wt.Father[bccno[i]]] = i;
wt.is_cut[bccno[i]] = 1;
wt.value[wt.Father[bccno[i]]] = min(wt.value[wt.Father[bccno[i]]], w[i]);
}
wt.solve();
mmd.init();
int yy = 0;
for(int i = 1; i <= n; i ++){
Next[i] = first[bccno[i]];
first[bccno[i]] = i;
}
for(int i = 1; i <= bcc_cnt; i ++){
Left[i] = yy + 1;
for(int j = first[i]; j != -1; j = Next[j]){
++ yy;
mmd.x = yy;
mmd.y = w[j];
mmd.add(1, N, 1);
poss[j] = yy;
}
for(int j = he[i]; j != -1; j = ne[j]){
++ yy;
mmd.x = yy;
mmd.y = w[j];
mmd.add(1, N, 1);
poss_fa[j] = yy;
}
Right[i] = yy;
}
/*for(int i = 1; i <= n; i ++){
printf("%d ", bccno[i]);
}
printf("\n");*/
//if(m < n) wt.for_tree();
// wt.debug();
for(int i = 1; i <= q; i ++){
char str[5];
int u, v;
scanf("%s%d%d", str, &u, &v);
if(str[0] == 'C'){
w[u] = v;
mmd.x = poss[u];
mmd.y = v;
mmd.add(1, N, 1);
mmd.x = Left[bccno[u]];
mmd.y = Right[bccno[u]];
int st = mmd.query(1, N, 1);
wt.change(bccno[u], st);
if(iscut[u]){
mmd.x = poss_fa[u];
mmd.y = v;
mmd.add(1, N, 1);
mmd.x = Left[wt.Father[bccno[u]]];
mmd.y = Right[wt.Father[bccno[u]]];
int st = mmd.query(1, N, 1);
wt.change(wt.Father[bccno[u]], st);
}
}
else{
if(u == v) printf("%d\n", w[u]);
else printf("%d\n", wt.qmin(bccno[u], bccno[v]));
}
}
}
return 0;
}
inline void insert(int u, int v){
ff ++;
G[ff] = (node){u, v, head[u]};
head[u] = ff;
return;
}
inline int dfs(int u, int fa){
int lowu = pre[u] = ++ dfs_clock;
int child = 0;
for(int i = head[u]; i != -1; i = G[i].next){
node e = G[i];
if(!pre[e.to]){
S.push(e);
child ++;
int lowv = dfs(e.to, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u]){
iscut[u] = true;
bcc_cnt ++;
for(; ; ){
node h = S.top(); S.pop();
if(bccno[h.from] != bcc_cnt) {
next1[++ dark] = head1[h.from];
head1[h.from] = dark;
kt[dark] = bcc_cnt;
bccno[h.from] = bcc_cnt;
use_times[h.from] ++;
}
if(bccno[h.to] != bcc_cnt){
next1[++ dark] = head1[h.to];
head1[h.to] = dark;
kt[dark] = bcc_cnt;
bccno[h.to] = bcc_cnt;
use_times[h.to] ++;
}
if(h.from == u && h.to == e.to){
break;
}
}
}
}
else if(pre[e.to] < pre[u] && e.to != fa){
S.push(e);
lowu = min(lowu, pre[e.to]);
}
}
if(fa < 0 && child == 1) iscut[u] = 0;
return lowu;
}