「HNOI2010」城市建设（线段树分治，LCT/Kruskal）

洛谷

BZOJ

简要做法

LCT 做法

把每条边按两次修改之间以及头尾分成若干段，然后按出现时间线段树分治，LCT 维护最小生成树。

时间复杂度 $O(n+(m+q)\log q\log n)$ ，常数有点大，听说很难卡到满分，自己没写。

Kruskal 做法

还是线段树分治，但尝试用 Kruskal 算法求最小生成树。

然而，Kruskal 算法要求边权从小到大加入，直接线段树分治无法满足这个要求。

（注：为了严谨，你可以认为下文中在比较大小时给第 $i$ ($1\le i\le m$) 条边的边权加上了 $2^{-i}$，这样保证了 MST 是唯一的。当然，在代码中无需如此。）

可以观察到，随着分治区间越来越小，修改的边也越来越少，图中大多数的边是不会被修改的。正因如此，可以猜想，大多数边在或不在 MST 中是固定的，而我们需要关注的，只有那些因会修改的边的边权变化而既可能在 MST 中又可能不在 MST 中的边。

如果我们有一张图 $G=(V, E)$，其中 $E'\subseteq E$ 是以后会被修改的边，那么，如何求出那些无论 $E'$ 中的边边权如何变化都一定在 MST 中/一定不在 MST 中的边呢？

1. 将 $E'$ 中的边边权设为正无穷，求 MST，此时不在 $E'$ 中且不在 MST 中的边，无论 $E'$ 中的边边权如何变化，都不在 MST 中，下文中称这些边为“一类边”。
2. 将 $E'$ 中的边边权设为 $0$，求 MST，此时不在 $E'$ 中且在 MST 中的边，无论 $E'$ 中的边边权如何变化，都在 MST 中，下文中称这些边为“二类边”。

那么，在继续分治下去的过程中，我们就只需关注 $E'$ 中的边以及是一类边而不是二类边的边。

由于一类边最多有 $|V|-1$ 条，而二类边至少有 $|V|-1-|E'|$ 条，所以是一类边而不是二类边的边最多有 $|E'|$ 条，于是，向下分治时需要关注的边就不超过 $2|E'|$ 条。

虽然只需关注这些边，但二类边依然要在分治过程中保留（计算 MST 时并查集中要保留，最后边权要计入答案）。边权计入答案很好办，而保留在并查集中可以通过可回退并查集来实现。

一层分治中每个分治内会被修改的边加起来是 $O(m+q)$ 条，并查集要可回退，只能按秩合并。所以总时间复杂度是 $O(n+(m+q)\log(m+q)+(m+q)\log q\log n)$ 。

时间复杂度和 LCT 做法差不多（你愿意的话你可以说时间复杂度更大），但跑得飞快。

有个实现上的小细节：将 $E'$ 中的边边权设为无穷大和 $0$ 时不需要真的修改再排序，最后加入（其实可以直接不加入）/最先加入即可，而其它边的排序可以在主函数中完成，而在分治过程中保持原序。这样时间复杂度的瓶颈上就只有并查集而没有排序了（当然我说的是 (m+q)logqlogn 这个瓶颈，不是 (m+q)log(m+q) 这个瓶颈）。

Kruskal 做法参考代码

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

using namespace std;

typedef long long ll;

struct Edge
{
	int u, v, w, l, r;
	bool operator<(const Edge &b) const
	{
		return w < b.w;
	}
	
	bool change(int left, int right)
	{
		return (l > left && l <= right) || (r >= left && r < right);
	}
};

struct UFS
{
	vector<int> f, siz;
	
	struct Change
	{
		int x, y;
	};
	
	stack<Change> c;
	
	void init(int n)
	{
		f.resize(n + 1);
		siz.resize(n + 1, 1);
		for (int i = 0; i <= n; ++i) f[i] = i;
	}
	
	int find(int x)
	{
		return x == f[x] ? x : find(f[x]);
	}
	
	bool merge(int x, int y)
	{
		x = find(x);
		y = find(y);
		if (x == y) return false;
		if (siz[x] < siz[y]) swap(x, y);
		c.push({x, y});
		siz[x] += siz[y];
		f[y] = x;
		return true;
	}
	
	void rollback(int x)
	{
		while ((int)c.size() > x)
		{
			f[c.top().y] = c.top().y;
			siz[c.top().x] -= siz[c.top().y];
			c.pop();
		}
	}
	
	int status() const { return c.size(); }
} ufs;

vector<ll> ans;

void solve(int l, int r, vector<Edge> &e, ll delta = 0)
{
	if (l == r)
	{
		ans[l] = delta;
		int ver = ufs.status();
		for (int i = 0; i < (int)e.size(); ++i) if (ufs.merge(e[i].u, e[i].v)) ans[l] += e[i].w;
		ufs.rollback(ver);
		return;
	}
	vector<bool> ininf(e.size(), false), inzero(e.size(), false);
	int ver = ufs.status();
	for (int i = 0; i < (int)e.size(); ++i) if (!e[i].change(l, r)) ininf[i] = ufs.merge(e[i].u, e[i].v);
	ufs.rollback(ver);
	for (int i = 0; i < (int)e.size(); ++i) if (e[i].change(l, r)) ufs.merge(e[i].u, e[i].v);
	for (int i = 0; i < (int)e.size(); ++i)
	{
		if (!e[i].change(l, r) && ufs.merge(e[i].u, e[i].v))
		{
			inzero[i] = true;
			delta += e[i].w;
		}
	}
	int mid = (l + r) >> 1;
	vector<Edge> le, re;
	for (int i = 0; i < (int)e.size(); ++i)
	{
		if (e[i].change(l, r) || (ininf[i] && !inzero[i]))
		{
			if (e[i].l <= mid) le.push_back(e[i]);
			if (e[i].r > mid) re.push_back(e[i]);
		}
	}
	ufs.rollback(ver);
	for (int i = 0; i < (int)e.size(); ++i) if (inzero[i]) ufs.merge(e[i].u, e[i].v);
	solve(l, mid, le, delta);
	solve(mid + 1, r, re, delta);
	ufs.rollback(ver);
}

int main()
{
	int n, m, q;
	
	scanf("%d%d%d", &n, &m, &q);
	
	vector<Edge> e;
	vector<int> u(m), v(m), w(m), last(m, 1);
	
	for (int i = 0; i < m; ++i) scanf("%d%d%d", &u[i], &v[i], &w[i]);
	
	for (int i = 1; i <= q; ++i)
	{
		int p, x;
		scanf("%d%d", &p, &x);
		--p;
		if (i > 1) e.push_back({u[p], v[p], w[p], last[p], i - 1});
		last[p] = i;
		w[p] = x;
	}
	
	for (int i = 0; i < m; ++i) e.push_back({u[i], v[i], w[i], last[i], q});
	
	sort(e.begin(), e.end());
	
	ans.resize(q + 1);
	ufs.init(n);
	
	solve(1, q, e);
	
	for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
	
	return 0;
}