Tourists

题目链接：luogu CF487E

题目大意

给你一个无向图，然后点有点权。
然后每次可能会单点修改点权，或者询问两个点之间所有的路径中点权最小的点。

思路

看到这种所有路径不难想到圆方树。

然后我们考虑方点就是它连着的原点的最小值。
然后会发现如果有修改会每次被卡到 $O(n)$（大菊花）

然后考虑一个奇妙的方法，就是考虑这个图特殊的地方，它是一棵树。
那你被卡的原因是因为你要全部都更新，那更新是肯定要更新的，那问题是我们可不可以先只更新一部分，然后询问的时候把没有的部分弄上。
那树的结构的话我们是不是可以只弄儿子的，然后每次更新就只用更新父亲那个。

然后你想一下树链剖分的部分，那不就是除了 LCA 是方点要把它父亲弄上之外别的都没问题吗。

然后剩下的就简单了，就普通圆方树，普通树链剖分加线段树维护最小值。

代码

#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 100;
int n, m, q, w[N << 1], tot;
vector <int> G[N], GG[N << 1];
multiset <int> sum[N];

struct SLPF {
	int dfn[N << 1], son[N << 1], sz[N << 1], fa[N << 1], top[N << 1], a[N << 3], deg[N << 1], dy[N << 1];
	
	void dfs1(int now, int father) {
		sz[now] = 1; fa[now] = father; deg[now] = deg[father] + 1;
		for (int i = 0; i < GG[now].size(); i++) {int x = GG[now][i]; if (x == father) continue;
			dfs1(x, now); sz[now] += sz[x]; if (sz[x] > sz[son[now]]) son[now] = x;
		}
		if (now > n) {
			for (int i = 0; i < GG[now].size(); i++) {int x = GG[now][i]; if (x == father) continue;
				sum[now - n].insert(w[x]);
			}
			w[now] = *sum[now - n].begin();
		}
	}
	
	void dfs2(int now, int father) {
		dfn[now] = ++dfn[0]; dy[dfn[0]] = now;
		if (son[now]) {
			top[son[now]] = top[now]; dfs2(son[now], now);
		}
		for (int i = 0; i < GG[now].size(); i++) {int x = GG[now][i]; if (x == father || x == son[now]) continue;
			top[x] = x; dfs2(x, now);
		}
	}
	
	void up(int now) {
		a[now] = min(a[now << 1], a[now << 1 | 1]);
	}
	
	void build(int now, int l, int r) {
		if (l == r) {
			a[now] = w[dy[l]]; return ;
		}
		int mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	void change(int now, int l, int r, int pl) {
		if (l == r) {
			a[now] = w[dy[pl]]; return ;
		}
		int mid = (l + r) >> 1;
		if (pl <= mid) change(now << 1, l, mid, pl); else change(now << 1 | 1, mid + 1, r, pl);
		up(now);
	}
	
	int query(int now, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return a[now];
		}
		int mid = (l + r) >> 1, re = 2e9;
		if (L <= mid) re = min(re, query(now << 1, l, mid, L, R));
		if (mid < R) re = min(re, query(now << 1 | 1, mid + 1, r, L, R));
		return re;
	}
	
	int ask(int x, int y) {
		int re = 2e9;
		while (top[x] != top[y]) {
			if (deg[top[x]] < deg[top[y]]) swap(x, y);
			re = min(re, query(1, 1, tot, dfn[top[x]], dfn[x]));
			x = fa[top[x]];
		}
		if (deg[x] > deg[y]) swap(x, y);
		re = min(re, query(1, 1, tot, dfn[x], dfn[y]));
		if (x > n) re = min(re, w[fa[x]]);
		return re;
	}
}T;

struct YF_tree {
	int dfn[N], low[N], sta[N];
	
	void link(int x, int y) {GG[x].push_back(y); GG[y].push_back(x);}
	
	void tarjan(int now) {
		dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now;
		for (int i = 0; i < G[now].size(); i++) {int x = G[now][i];
			if (!dfn[x]) {
				tarjan(x); low[now] = min(low[now], low[x]);
				if (dfn[now] == low[x]) {
					tot++;
					while (sta[sta[0]] != x) {
						link(sta[sta[0]], tot); sta[0]--;
					}
					link(sta[sta[0]], tot); sta[0]--;
					link(now, tot);
				}
			}
			else low[now] = min(low[now], dfn[x]);
		}
	}
	
	void Init() {
		tot = n;
		for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
		T.dfs1(1, 0); T.dfs2(1, 0);
	}
}H;

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	for (int i = 1; i <= m; i++) {
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y); G[y].push_back(x); 
	}
	
	H.Init();
	T.build(1, 1, tot);
	
	while (q--) {
		char c = getchar(); while (c != 'C' && c != 'A') c = getchar();
		if (c == 'A') {
			int x, y; scanf("%d %d", &x, &y);
			printf("%d\n", T.ask(x, y));
		}
		else {
			int x, y; scanf("%d %d", &x, &y);
			if (T.fa[x]) {
				sum[T.fa[x] - n].erase(w[x]); sum[T.fa[x] - n].insert(y);
				w[T.fa[x]] = *sum[T.fa[x] - n].begin(); T.change(1, 1, tot, T.dfn[T.fa[x]]);
			}
			w[x] = y; T.change(1, 1, tot, T.dfn[x]);
		}
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145