「UR #5」怎样更有力气 - 并查集

给定一棵 $n$ 个节点的树，有 $m$ 天修路

每一天修一条路的花费固定，为 $w _i(1 \le i \le m)$。第 $i$ 天会指定两个点 $u, v$，在第 $i$ 天时只可以在树中 $u$ 到 $v$ 的链上的任意两点之间修路。同时还有 $p$ 条限制 $(t, a, b)$，表示第 $t$ 天不能在 $a, b$ 之间修路

问最小生成树的总花费。保证无自环重边，$a, b$ 在 $u _t, v _t$ 的路径上，且一定有一个合法生成树。

Link

UOJ61

Solution

xhb写得很好，这里就直接搬过来了

采用 Kruskal。把天数按 $w _i$ 从小到大排序，那么每天都是让能连的边尽量连。

考虑优化这个连边的过程。

有一个小 trick: 设 $k$ 为当天限制的个数，如果 $k <dis(u, v)$，那么 $u$ 到 $v$ 的这条链上的点一定会被连到一个联通块里去。

证明显然

所以当 $k < d$ 时可以直接链并，总复杂度 。

考虑当 $k \ge d$ 时怎么办。这时可以把 $u$ 到 $v$ 链上的点全部扒下来考虑，因为 $d \le k$ 且 $\sum k = p$，所以扒下来的总点数不超过 $p$，没有问题。

这时把限制抽象成图，可以得到一张 $d + 1$ 个点 $k$ 条边的无向图。这是可连边的图的补图。

有一个经典结论，一个无向图中最小的点的度数是 的。

设其最小度数为 $d$，那么有 $d \le \frac {2m} n, d < n$。$\therefore d ^2 < dn \le 2m$。

于是把这个限制图上的最小度数的点 $x$ 拿出来，与它连边的那些点记为集合 $T$，$T$ 的补集记为 $S$。

$S$ 包含了 $x$ 以及没有与 $x$ 限制边相连的点，那些点直接与 $x$ 并成一个联通块就行了。

现在考虑 $T$。显然只有两种连边方式：$T \to T, S \to T$。

$T \to T$：对于 $x$ 暴力枚举与其有限制边相连的两个点，并判断这两点是否有限制边。无则合并。

$S \to T$：对于 $T$ 中的每一个点枚举与其有限制边相连的点，并判断有多少个是 $S$ 集合中的点。如果 $S$ 中的点全部与其相连，无法连边；否则其一定能与 $S$ 中某个集合合并，且因为 $S$ 中所有点都与 $x$ 合并，故直接无视限制边与 $x$ 合并。

时间复杂度分别是 和 ，易知这是 的。合并需要用到并查集，所以总复杂度大概是

Code(6.1K)

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 3e5 + 100;

LL ans;
int N, M, P, Left;
int e, Begin[Maxn], To[Maxn], Next[Maxn];
struct road
{
	int x, y, z, id;
	inline int operator < (const road &rhs) const { return z < rhs.z; }
} E[Maxn];
vector <pii> Ban[Maxn];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

namespace DSU
{
	int fa[Maxn];
	inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i; }
	inline int get_fa (int x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }
	inline void link (int x, int y, int w) 
	{ 
		x = get_fa (x), y = get_fa (y);
		if (x != y) fa[get_fa (x)] = get_fa (y), ans += w, ++Left; 
	}
	inline int check (int x, int y) { return get_fa (x) == get_fa (y); }
}

namespace HLD
{
	int fa[Maxn], size[Maxn], dep[Maxn], son[Maxn], top[Maxn];

	inline void dfs (int x)
	{
		dep[x] = dep[fa[x]] + 1;
		size[x] = 1;
		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (y == fa[x]) continue;
			fa[y] = x;
			dfs (y);
			if (size[y] > size[son[x]]) son[x] = y;
			size[x] += size[y];
		}
	}

	inline void dfs (int x, int now)
	{
		top[x] = now;
		if (son[x]) dfs (son[x], now);
		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (y == fa[x] || y == son[x]) continue;
			dfs (y, y);
		}
	}

	inline void init () { dfs (1), dfs (1, 1); }

	inline int get_lca (int x, int y)
	{
		while (top[x] != top[y])
		{
			if (dep[top[x]] < dep[top[y]]) swap (x, y);
			x = fa[top[x]];
		}
		if (dep[x] > dep[y]) swap (x, y);
		return x;
	}

	inline int get_dis (int x, int y) { return dep[x] + dep[y] - 2 * dep[get_lca (x, y)]; }
}

using namespace HLD;

namespace TREE
{
	namespace DSU
	{
		int fa[Maxn];
		inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i; }
		inline int get_fa (int x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }
		inline void link (int x, int y, int w) // 把x连到y上（y是x的父亲）
		{ 
			x = get_fa (x), y = get_fa (y);
			:: DSU :: link (x, y, w);
			fa[x] = y;
		}
		inline int check (int x, int y) { return get_fa (x) == get_fa (y); }
	}

	inline void init () { HLD :: init (); DSU :: init (); }

	inline void solve (int x, int y, int w)
	{
		int lca = HLD :: get_lca (x, y);
		while (!DSU :: check (x, lca))
		{
			DSU :: link (x, fa[x], w);
			x = DSU :: get_fa (x);
		}
		while (!DSU :: check (y, lca))
		{
			DSU :: link (y, fa[y], w);
			y = DSU :: get_fa (y);
		}
	}
}

namespace GRA
{
	int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
	int deg[Maxn];
	vector <int> A, S, T;
	int o, vis[Maxn];
	int is_S[Maxn], is_T[Maxn];

	inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; ++deg[x]; }

	inline void get_chain (int x, int y)
	{
		A.clear (), S.clear (), T.clear ();
		int lca = HLD :: get_lca (x, y);
		while (x != lca) A.pb (x), x = fa[x];
		while (y != lca) A.pb (y), y = fa[y];
		A.pb (lca);
	}

	inline void init (int id)
	{
		e = 0;
		for (int i = 0; i < A.size(); ++i) Begin[A[i]] = deg[A[i]] = 0;

		for (int j = 0; j < Ban[id].size(); ++j)
		{
			int x = Ban[id][j].x, y = Ban[id][j].y;
			add_edge (x, y);
			add_edge (y, x);
		}

		o = -1;
		for (int i = 0; i < A.size(); ++i)
		{
			vis[A[i]] = 0;
			if (o < 0 || deg[A[i]] < deg[o]) 
				o = A[i];
		}
	}

	inline void get_set ()
	{
		for (int i = Begin[o]; i; i = Next[i])
		{
			int x = To[i];
			if (!vis[x]) T.pb (x);
			vis[x] = 1;
		}

		for (int i = 0; i < A.size(); ++i) if (!vis[A[i]]) S.pb (A[i]);

		for (int i = 0; i < S.size(); ++i) is_S[S[i]] = 1, is_T[S[i]] = 0;
		for (int i = 0; i < T.size(); ++i) is_T[T[i]] = 1, is_S[T[i]] = 0;
	}

	inline void solve_S (int w)
	{
		for (int i = 0; i < S.size(); ++i)
		{
			int x = S[i];
			DSU :: link (x, o, w);
		}
	}

	inline void solve_T (int w)
	{
		for (int i = 0; i < A.size(); ++i) vis[A[i]] = 0;
		for (int t = 0; t < T.size(); ++t)
		{
			int x = T[t];
			int cnt = 0;
			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				if (is_S[y]) ++cnt;
				if (is_T[y]) vis[y] = 1;
			}

			if (cnt != S.size()) DSU :: link (o, x, w);

			for (int j = t + 1; j < T.size(); ++j)
			{
				int y = T[j];
				if (!vis[y])
					DSU :: link (x, y, w);
			}

			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				vis[y] = 0;
			}
		}
	}

	inline void solve (int x, int y, int w, int id)
	{
		get_chain (x, y), init (id);
		get_set ();
		solve_S (w), solve_T (w);
	}
}

inline void Init ()
{
	DSU :: init ();
	TREE :: init ();
}

inline void Solve ()
{
	Init ();

	sort (E + 1, E + M + 1);
	for (int i = 1; i <= M && Left < N - 1; ++i)
	{
		int x = E[i].x, y = E[i].y, w = E[i].z, id = E[i].id, k = Ban[id].size();
		int dis = get_dis (x, y);
		if (k < dis) TREE :: solve (x, y, w);
		else GRA :: solve (x, y, w, id);
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), P = read<int>();
	for (int i = 2; i <= N; ++i) add_edge (read<int>(), i);
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>(), z = read<int>();
		E[i] = (road){x, y, z, i};
	}
	for (int i = 1; i <= P; ++i)
	{
		int t = read<int>(), a = read<int>(), b = read<int>();
		Ban[t].pb (mp (a, b));
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}