UOJ#30 图连通性+树链剖分+线段树

题目大意：

给定一个连通无向图，每次求对于从$a$出发到$b$的所有点最多经过一次的路径中，使得路径上点权最小值最小的路径的点权最小值是多少。

数据范围$n,m,q\leq{100000}$。

题解：

首先需要注意到，对于一个点双，其中如果存在三个不同的$x,y,z$，则必定存在一条从$x$出发到$z$结束且不重复经过任何一个点的路径，使得路径经过$y$。

这个我现在还不是非常会证。

那么我们不妨利用点双形成的树，给每个点双记录一下点双里面所有的点的权值最小值，那么答案就是树上的路径的点权最小值。

但是当我们修改时，对于一个割点，如果这个点的权值发生变化，我们需要维护所有这个割点所属的点双，而这个数目可能会很多。

我们重建一棵树，给每个点双建立一个虚点，他的父亲是这个点双的根节点，同时每个原来图中的节点的父亲是他的父亲点双代表的虚点。

我们考虑每个点只会对于他的父亲点双的权值以及自身的权值造成影响，这样的话，考虑两个询问点的LCA，如果是虚点则答案还要再对虚点的父亲（这个点双的根节点）取最小值。

如何维护点双的权值，由于需要支持动态插入删除求最值，我们用一个set维护就行了。

时间复杂度$O((n+q)logn)$。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}
int getint() {
	int c;
	while (!isdigit(c = getc()));
	int x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}
char getch() {
	char c;
	while ((c = getc()) != 'C' && c != 'A');
	return c;
}

char buf[100010 * 12], *o = buf;
void print(int x) {
	static short stack[11], top;
	if (!x)
		*o++ = '0';
	else {
		for (top = 0; x; stack[top++] = x % 10, x /= 10);
		while (top--)
			*o++ = '0' + stack[top];
	}
	*o++ = '\n';
}

int n, m, q;
int head[100010], nxt[200010], to[200010];
void addedge(int a, int b) {
	static int q = 1;
	to[q] = b;
	nxt[q] = head[a];
	head[a] = q++;
}
void make(int a, int b) {
	//printf("%d %d\n", a, b);
	addedge(a, b);
	addedge(b, a);
}

int w[100010];

int dfn[100010], low[100010], stack[100010], top, tclock, cnt, y;
vector<int> bel[100010], node[100010];
multiset<int> v[100010];
void Tarjan(int x) {
	dfn[x] = low[x] = ++tclock;
	stack[++top] = x;
	for (int j = head[x]; j; j = nxt[j]) {
		if (!dfn[to[j]]) {
			Tarjan(to[j]);
			low[x] = min(low[x], low[to[j]]);
			if (low[to[j]] >= dfn[x]) {
				++cnt;
				while (1) {
					y = stack[top--];
					bel[y].push_back(cnt);
					node[cnt].push_back(y);
					//v[cnt].insert(w[y]);
					if (y == to[j])
						break;
				}
				bel[x].push_back(cnt);
				node[cnt].push_back(x);
				//v[cnt].insert(w[x]);
			}
		}
		else
			low[x] = min(low[x], dfn[to[j]]);
	}
}

int Root;
int bcc_id[100010];
struct Tree {
	int head[200010], nxt[200010], to[200010], w[200010];
	int pa[200010], dep[200010], siz[200010], son[200010];
	int top[200010], p_id[200010], id_p[200010], id;
	void addedge(int a, int b) {
		static int q = 1;
		to[q] = b;
		nxt[q] = head[a];
		head[a] = q++;
	}
	void dfs(int x) {
		siz[x] = 1;
		int mx = 0;
		for (int j = head[x]; j; j = nxt[j]) {
			pa[to[j]] = x;
			dep[to[j]] = dep[x] + 1;
			dfs(to[j]);
			siz[x] += siz[to[j]];
			if (siz[to[j]] > mx) {
				mx = siz[to[j]];
				son[x] = to[j];
			}
		}
	}
	void create(int x, int Top) {
		top[x] = Top;
		p_id[x] = ++id;
		id_p[id] = x;
		if (son[x])
			create(son[x], Top);
		for (int j = head[x]; j; j = nxt[j])
			if (to[j] != pa[x] && to[j] != son[x])
				create(to[j], to[j]);
	}
	void init() {
		dep[Root] = 1;
		dfs(Root);
		create(Root, Root);
	}
	int queryLca(int x, int y) {
		while (top[x] != top[y]) {
			if (dep[top[x]] < dep[top[y]])
				swap(x, y);
			x = pa[top[x]];
		}
		if (dep[x] < dep[y])
			swap(x, y);
		return y;
	}
}myTree;

struct SegmentTree {
	int a[530010], M;
	void init(int n) {
		for (M = 1; M < (n + 2); M <<= 1);
		memset(a, 0x3f, sizeof a);
		for (int i = 1; i <= n; ++i)
			a[M + i] = myTree.w[myTree.id_p[i]];
		for (int i = M - 1; i >= 1; --i)
			a[i] = min(a[i << 1], a[i << 1 ^ 1]);
	}
	int query(int tl, int tr) {
		int re = 0x3f3f3f3f;
		for (tl += M - 1, tr += M + 1; tl ^ tr ^ 1; tl >>= 1, tr >>= 1) {
			if (~tl & 1)
				re = min(re, a[tl ^ 1]);
			if (tr & 1)
				re = min(re, a[tr ^ 1]);
		}
		return re;
	}
	void modify(int x, int v) {
		for (a[x += M] = v, x >>= 1; x; x >>= 1)
			a[x] = min(a[x << 1], a[x << 1 ^ 1]);
	}
}Seg;

int query(int x, int y) {
	int ans = 0x3f3f3f3f;
	while (myTree.top[x] != myTree.top[y]) {
		if (myTree.dep[myTree.top[x]] < myTree.dep[myTree.top[y]])
			swap(x, y);
		ans = min(ans, Seg.query(myTree.p_id[myTree.top[x]], myTree.p_id[x]));
		x = myTree.pa[myTree.top[x]];
	}
	if (myTree.dep[x] < myTree.dep[y])
		swap(x, y);
	return min(ans, Seg.query(myTree.p_id[y], myTree.p_id[x]));
}

void dfs(int x, int id) {
	int y;
	//myTree.w[n + id] = *v[id].begin();
	myTree.addedge(x, n + id);
	for (int i = 0; i < node[id].size(); ++i) {
		if ((y = node[id][i]) != x) {
			myTree.addedge(n + id, y);
			bcc_id[y] = id;
			for (int j = 0; j < bel[y].size(); ++j) {
				if (bel[y][j] != id)
					dfs(y, bel[y][j]);
			}
		}
	}
}

int main() {
	//freopen("tt.in", "r", stdin);
	n = getint(), m = getint(), q = getint();
	int i, j, a, b;
	for (i = 1; i <= n; ++i)
		w[i] = getint();
	while (m--) {
		a = getint();
		b = getint();
		make(a, b);
	}
	
	Tarjan(1);

	for (i = 1; i <= n; ++i) {
		if (bel[i].size() == 1) {
			Root = i;
			bcc_id[Root] = bel[Root][0];
			dfs(Root, bel[Root][0]);
			break;
		}
	}
	for (i = 1; i <= n; ++i)
		v[bcc_id[i]].insert(w[i]);
	for (i = 1; i <= n; ++i)
		myTree.w[i] = w[i];
	for (i = 1; i <= cnt; ++i)
		myTree.w[n + i] = *v[i].begin();
	
	myTree.init();
	
	Seg.init(n + cnt);
	
	char type;
	int new_w;
	
	int lca, ans;
	while (q--) {
		type = getch();
		if (type == 'A') {
			a = getint();
			b = getint();
			lca = myTree.queryLca(a, b);
			ans = query(a, b);
			if (lca > n && myTree.pa[lca] != 0)
				ans = min(ans, myTree.w[myTree.pa[lca]]);
			print(ans);
		}
		else {
			a = getint();
			new_w = getint();
			v[bcc_id[a]].erase(v[bcc_id[a]].find(myTree.w[a]));
			v[bcc_id[a]].insert(new_w);
			Seg.modify(myTree.p_id[n + bcc_id[a]], *v[bcc_id[a]].begin());
			myTree.w[a] = new_w;
			Seg.modify(myTree.p_id[a], new_w);
		}
	}
	
	fwrite(buf, o - buf, 1, stdout);
	fflush(stdout);
	
	return 0;
}