[algorithm learning] square tree

catalog

As we all know, trees (or forests) have good properties and are easy to maintain through many common data structures.

However, general graphs do not have such good properties. Fortunately, sometimes we can turn some problems on general graphs into trees.

The square tree is a way to turn a graph into a tree. This paper introduces the construction, properties and some applications of the square tree.

Limited to space, some conclusions in this paper have not been proved, readers can understand or prove by themselves.

1, The definition of square tree

The cube tree was originally a tool for dealing with "cactus graph" (undirected graph with no more than one edge in a simple ring), but we can use it on general undirected graph sometimes to explore its more properties.

In order to introduce the circular square tree, we first introduce the point double connected component.

A definition of a point double connected graph is that there are at least two paths between any two different points.
Point non repetition not only means that the point on the path is not repeated (simple path), but also that the intersection of the two paths is empty (of course, the path must pass through the starting point and the arrival point, which is not considered).

It can be found that for a graph with only one point, it is difficult to define whether it is a point double. Here, we do not consider the graph with a node number of \ (1 \).

An almost equivalent definition is: a graph without cut points.
This definition is only valid when there are only two points in a graph, and one edge connects them. It has no cut points, but it can't find two paths that don't intersect because there is only one path.
(it can also be understood that the path can be counted twice, but it does not cross because it does not pass through other points.)

Although the original definition is the former, for convenience, we stipulate that the latter should be used in the definition of point double graph.

The vertex biconnected component of a graph is a maximal vertex biconnected subgraph.
Different from strongly connected components, a point may belong to multiple point pairs, but an edge belongs to exactly one point pair (if the former is used, it may not belong to any point pair).

In the square tree, each point corresponds to a circle, and each point corresponds to a square.
So there are \ (n+c \) points, where \ (n \) is the number of original points and \ (c \) is the number of double connected components of original points.

For each point of the double connected component, its corresponding square point is connected to each point of the double connected component.
Each point pair forms a "chrysanthemum chart", and multiple "chrysanthemum charts" are connected by the cut points in the original picture (because the separation point of point pair is the cut point).

Obviously, each edge of the square tree connects a dot and a square.

Here is a graph, PPT from WC, showing the corresponding point double and square tree shapes of a graph.

The number of points in the square tree is less than \ (2n \), because the number of cut points is less than \ (n \), so please note that the size of various arrays should be doubled.

In fact, if the original graph is connected, the "cube tree" is a tree. If the original graph has \ (k \) connected components, its cube tree will also form a forest of \ (k \) trees.

If there is only one point for a connected component in the original graph, it needs to be analyzed in detail. We will not consider isolated points in the following discussion.

2, Construction of the square tree

For a graph, how to construct its cube tree? First of all, we can find that if the graph is not connected, it can be divided into every connected subgraph, so we only consider the connected graph.

Because the circular square tree is based on the point double connected component, and the point double connected component is based on the cut point, so we only need to use the similar method to find the cut point.

Tarjan algorithm is a common algorithm for finding cut points. If you can understand the following content, it's very simple. If you can't, it's OK.

We skip Tarjan's cut point and directly introduce the algorithm used by the square tree (actually a variant of Tarjan):

DFS the graph, and two key arrays dfn and low (similar to Tarjan) are used in the middle.

dfn[u] stores the DFS order of node \ (U \), that is, when it first accesses \ (U \), it is the first node to be accessed.
low[u] stores the minimum DFS order of a point \ (v \) in the subtree of the DFS tree of node \ (U \) that can be accessed by at most one atavism edge or to the edge of the parent tree.
If you haven't heard of Tarjan algorithm, it may be a little difficult to understand. Let's take an example:

(it can be found that this picture is actually equivalent to the picture in the above picture.)
Here, the tree edge is drawn in straight lines from top to bottom, and the atavism edge is drawn in curves from bottom to top. The node number is its DFS sequence.

The low array is as follows:

\(i\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\)
\(\mathrm{low}[i]\) \(1\) \(1\) \(1\) \(3\) \(3\) \(4\) \(3\) \(3\) \(7\)

It's not hard to understand. Note that the low of \ (9 \) here is \ (7 \), which is different from some methods of seeking cut points. For convenience, we stipulate that we can go up through the parent side, but the main idea is the same.

We can easily write out DFS functions to calculate dfn and low (initially, the dfn array is cleared):

void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc; // low is initialized to the current node dfn
	for (auto v : G[u]) { // Traversing the adjacent nodes of u
		if (!dfn[v]) { // If not visited
			Tarjan(v); // recursion
			low[u] = std::min(low[u], low[v]); // Not accessed and low take min
		}
		else low[u] = std::min(low[u], dfn[v]); // Accessed and dfn take min
	}
}

Next, we consider point pairs and DFS trees, as well as the association between the two arrays.

It can be found that each point pair is a straight up and down chain on the DFS tree and contains at least two points, and each tree edge is exactly within one point pair.

We consider a point double in the top node \ (u \) of DFS tree, and determine the point double at \ (u \), because the subtree of \ (u \) contains the information of the whole point double.

Because there are at least two points, considering the next point \ (v \) of this point pair, there is \ (u \), and there is a tree edge between \ (v \).

It's not hard to find that there must be \ (\ mathrm{low}[v]=\mathrm{dfn}[u] \).
More precisely, for a tree edge \ (u\to v \), \ (u,v \) is in the same point pair, and \ (U \) is the node with the shallowest depth in the point pair if and only if \ (\ mathrm{low}[v]=\mathrm{dfn}[u] \).

Then we can determine where point pairs exist in DFS process, but we can't exactly determine the point set of a point pair.

This is not difficult to deal with. We can maintain a stack in the DFS process, and the storage has not yet determined the node that belongs to point double (there may be multiple nodes).

When finding point pairs, all the points except \ (u \) in point pairs are concentrated at the top of the stack, just keep popping the stack until \ (v \) pops up.

Of course, we can handle the pop-up node at the same time, as long as it is connected with the new square point. Finally, you need to connect \ (u \) and the square point.

In this way, we can complete the construction of the square tree naturally. We can label the square point as an integer starting with \ (n+1 \), which can effectively distinguish the circle point and the square point.

This part may not be clear enough. Here is a code with detailed comments, output statements and samples to help understand. It is recommended that readers copy the code and practice to understand it. After all, the code is the most helpful (don't forget to open c++11).

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
	printf("  Enter : #%d\n", u);
	low[u] = dfn[u] = ++dfc; // low is initialized to the current node dfn
	stk[++tp] = u; // Add to stack
	for (auto v : G[u]) { // Traversing the adjacent nodes of u
		if (!dfn[v]) { // If not visited
			Tarjan(v); // recursion
			low[u] = std::min(low[u], low[v]); // Not accessed and low take min
			if (low[v] == dfn[u]) { // It means finding a point biconnected component based on u
				++cnt; // Increase the number of square points
				printf("  Found a New BCC #%d.\n", cnt - N);
				// Backstack the points except u in point pairs and connect the edges in the square tree
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
					printf("    BCC #%d has vertex #%d\n", cnt - N, x);
				}
				// Note that u itself should be connected (but not backstacked)
				T[cnt].push_back(u);
				T[u].push_back(cnt);
				printf("    BCC #%d has vertex #%d\n", cnt - N, u);
			}
		}
		else low[u] = std::min(low[u], dfn[v]); // Accessed and dfn take min
	}
	printf("  Exit : #%d : low = %d\n", u, low[u]);
	printf("  Stack:\n    ");
	for (int i = 1; i <= tp; ++i) printf("%d, ", stk[i]);
	puts("");
}

int main() {
	scanf("%d%d", &N, &M);
	cnt = N; // Dot double / square dot label starts from N
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v); // Add two-way edge
		G[v].push_back(u);
	}
	// Dealing with disconnected graphs
	for (int u = 1; u <= N; ++u)
		if (!dfn[u]) Tarjan(u), --tp;
		// Notice that when you exit Tarjan, there is another element in the stack, namely root, which will be removed from the stack
	return 0;
}

Provide a test case:

13 15
1 2
2 3
1 3
3 4
3 5
4 5
5 6
4 6
3 7
3 8
7 8
7 9
10 11
11 10
11 12

The graph corresponding to this example (including the case of multiple edges and isolated points):

3, Application of the square tree

Let's talk about some examples that can be solved by using the circular square tree.

[APIO2018] Triathlon

This problem can be regarded as the template of the square tree.

Brief introduction:

Given a simple undirected graph, ask how many pairs of triples \ (\ LANGLE s,c,f \ range \) (\ (s,c,f \) are different from each other) make a simple path from \ (s \) to \ (t \) through \ (c \).

Explanation:

When it comes to simple paths, we must mention a good property about point pairs: for two points in a point pair, the union of simple paths between them is exactly equal to this point pair.
That is to say, there must be a simple path between two different points \ (u,v \) in the same point pair passing another point \ (w \) in the same point pair.

Proof of this nature:

  • Obviously, if the simple path has point double, it is impossible to return to this point double, otherwise it will conflict with the definition of point double.

  • So we only need to prove that there must be a simple path from \ (u \) to \ (v \) in any three different points \ (u,v,c \) of a point doubly connected graph.

  • First, we exclude the case where the number of points is \ (2 \), which satisfies this property, but we can't get \ (3 \) different points.

  • For the rest of the cases, the network flow model should be established. The connection capacity of the source point to \ (c \) is \ (2 \), and the connection capacity of the source point to \ (u \) and \ (v \) to the sink point is \ (1 \).

  • The two-way edge \ (\ LANGLE x, y \ range \) in the original image becomes \ (x \) to \ (Y \) and \ (Y \) to \ (1 \) and \ (Y \) to \ (x \) as well.

  • Finally, assign \ (1 \) capacity to every point except source point, sink point and \ (c \), which can be achieved by splitting points.

  • Because the capacity from the source point to the edge of \ (c \) is \ (2 \), if the maximum flow of this network is \ (2 \), it is proved that there must be a path through \ (c \).

  • Considering the maximum flow minimum cut theorem, it is obvious that the minimum cut is less than or equal to \ (2 \), and then as long as we prove that the minimum cut is greater than \ (1 \).

  • This is equivalent to proving that cutting off any edge with a capacity of \ (1 \) can not make the source point and sink point disconnected.

  • In consideration of cutting off the connection points of \ (u \) or \ (v \) and sink points, according to the first definition of point pair, there must be a simple path from \ (c \) to another point that has not been cut off.

  • Consider cutting off the edge formed by a node split point, which is equivalent to deleting a point. According to the second definition of point pair, the remaining graphs are still connected.

  • Consider cutting an edge built from the original edge, which is equivalent to deleting an edge, which is weaker than deleting a point, and there is obviously a path.

  • So we prove that the minimum cut is greater than \ (1 \), that is, the maximum flow is equal to \ (2 \). The proof is over.

What can this conclusion tell us? It tells us that when we consider the path of two points on the square tree, the set of points adjacent to the passing square points on the path is equal to the set of points on the simple path of two points in the original image.

Back to the topic, consider fixing \ (s \) and \ (f \), and find the number of legal \ (c \). Obviously, the number of legal \ (c \) is equal to the number of points minus \ (2 \) of the union of simple paths between \ (s,f \) (excluding \ (s,f \) itself).

Then, after the square tree is built for the original drawing, the number of simple paths between two points is related to the number of square points (point pairs) and circle points they pass through on the square tree.

Next is a common skill of circular square tree: when the path statistics, the points are assigned with appropriate weights.
In this problem, the weight of each square point is the size of the corresponding point pair, and the weight of each circle point is \ (- 1 \).

In this way, the weight sum of path points on the square tree between the two points is exactly equal to the size of the simple path Union in the original drawing minus \ (2 \).

The problem is transformed into the sum of the path weights of two points on the statistical square tree.

From another point of view, instead of counting the contribution of each point to the answer, that is, the weight is multiplied by the number of paths passing through it, which can be calculated by a simple tree DP.

Finally, don't forget to deal with disconnected graphs. Here is the corresponding code:

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];
long long Ans;

int dfn[MN], low[MN], dfc, num;
int stk[MN], tp;

int wgh[MN * 2];

void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	++num;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				wgh[++cnt] = 0;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
					++wgh[cnt];
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
				++wgh[cnt];
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}

int vis[MN * 2], siz[MN * 2];

void DFS(int u, int fz) {
	vis[u] = 1;
	siz[u] = (u <= N);
	for (auto v : T[u]) if (v != fz) {
		DFS(v, u);
		Ans += 2ll * wgh[u] * siz[u] * siz[v];
		siz[u] += siz[v];
	}
	Ans += 2ll * wgh[u] * siz[u] * (num - siz[u]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int u = 1; u <= N; ++u) wgh[u] = -1;
	cnt = N;
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int u = 1; u <= N; ++u) if (!dfn[u]) {
		num = 0;
		Tarjan(u), --tp;
		DFS(u, 0);
	}
	printf("%lld\n", Ans);
	return 0;
}

By the way, the answer to this question is \ (212 \).

[CodeForces 487E]Tourists

Brief introduction:

Given a simple undirected connected graph, two operations are required:

  1. Modify the point weight of a point.

  2. Ask the minimum value of point weight on all simple paths between two points.

Explanation:

In the same way, we build the square tree of the original graph and make the weight of the square point the minimum value of the weight of the adjacent circle point. The problem is transformed into finding the minimum value on the path.

The path minimum can be maintained by tree chain segmentation and segment tree, but what about modification?

To modify the point weight of a circle point at a time, you need to modify all adjacent square points, so it is easy to get stuck in \ (\ mathcal{O}(n) \) modifications.

At this time, we make use of the property that the square tree is a tree, and make the weight of the square point the minimum value of the weight of his son's circle point. In this way, only the father's Square point needs to be modified.

For the maintenance of square points, only one multiset maintenance weight set is needed for each square point.

It should be noted that when querying, if LCA is a square point, it is also necessary to check the weight of LCA's parent dot.

Note: the number of points of the round square tree should be twice of that of the original drawing, otherwise the array will cross the boundary, resulting in a metaphysical error.

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

const int MN = 100005;
const int MS = 524288;
const int Inf = 0x7fffffff;

int N, M, Q, cnt;
int w[MN * 2];
std::vector<int> G[MN], T[MN * 2];
std::multiset<int> S[MN * 2];

int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				++cnt;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}

int idf[MN * 2], faz[MN * 2], siz[MN * 2], dep[MN * 2], son[MN * 2], top[MN * 2];

void DFS0(int u, int fz) {
	faz[u] = fz, dep[u] = dep[fz] + 1, siz[u] = 1;
	for (auto v : T[u]) if (v != fz) {
		DFS0(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v]) son[u] = v;
	}
}

void DFS1(int u, int fz, int tp) {
	dfn[u] = ++dfc, idf[dfc] = u, top[u] = tp;
	if (son[u]) DFS1(son[u], u, tp);
	for (auto v : T[u])
		if (v != fz && v != son[u])
			DFS1(v, u, v);
}

#define li (i << 1)
#define ri (i << 1 | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r

int dat[MS];

void Build(int i, int l, int r) {
	if (l == r) { dat[i] = w[idf[l]]; return ; }
	Build(ls), Build(rs);
	dat[i] = std::min(dat[li], dat[ri]);
}

void Mdf(int i, int l, int r, int p, int x) {
	if (l == r) { dat[i] = x; return ; }
	if (p <= mid) Mdf(ls, p, x);
	else Mdf(rs, p, x);
	dat[i] = std::min(dat[li], dat[ri]);
}

int Qur(int i, int l, int r, int a, int b) {
	if (r < a || b < l) return Inf;
	if (a <= l && r <= b) return dat[i];
	return std::min(Qur(ls, a, b), Qur(rs, a, b));
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &w[i]);
	cnt = N;
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	Tarjan(1), DFS0(1, 0), dfc = 0, DFS1(1, 0, 1);
	for (int i = 1; i <= N; ++i) if (faz[i])
		S[faz[i]].insert(w[i]);
	for (int i = N + 1; i <= cnt; ++i)
		w[i] = *S[i].begin();
	Build(1, 1, cnt);
	for (int q = 1; q <= Q; ++q) {
		char opt[3]; int x, y;
		scanf("%s%d%d", opt, &x, &y);
		if (*opt == 'C') {
			Mdf(1, 1, cnt, dfn[x], y);
			if (faz[x]) {
				int u = faz[x];
				S[u].erase(S[u].lower_bound(w[x]));
				S[u].insert(y);
				if (w[u] != *S[u].begin()) {
					w[u] = *S[u].begin();
					Mdf(1, 1, cnt, dfn[u], w[u]);
				}
			}
			w[x] = y;
		}
		else {
			int Ans = Inf;
			while (top[x] != top[y]) {
				if (dep[top[x]] < dep[top[y]])
					std::swap(x, y);
				Ans = std::min(Ans, Qur(1, 1, cnt, dfn[top[x]], dfn[x]));
				x = faz[top[x]];
			}
			if (dfn[x] > dfn[y]) std::swap(x, y);
			Ans = std::min(Ans, Qur(1, 1, cnt, dfn[x], dfn[y]));
			if (x > N) Ans = std::min(Ans, w[faz[x]]);
			printf("%d\n", Ans);
		}
	}
	return 0;
}

[SDOI2018] strategy game

Brief introduction:

A simple undirected connected graph is given. \ (q \) queries:

Given a point set \ (S \) (\ (2 \ le|S| \ Le n \), ask how many points \ (u \) satisfy \ (u \ not in S \) and the points in \ (S \) are not all in a connected component after \ (u \) is deleted.

Each test point has multiple sets of data.

Explanation:

First, the number of dots in the connected subgraph corresponding to the query \ (S \) on the circular square tree is subtracted from \ (| S \).

How to calculate the number of dots in a connected subgraph? There is a way:

Put the weight of the dot on the edge of it and its father's Square. The problem is transformed into the sum of the edge weight. For this problem, please refer to the solution method of this question: Luogu P3320: bzoj 3991: LOJ 2182: [SDOI2015] treasure hunt game.
That is, sort the points in \ (S \) in DFS order, and calculate the distance sum of the two adjacent points after sorting. The answer is half of the distance sum, because each edge is only passed twice.

Finally, if the shallowest node in the subgraph is a dot, \ (1 \) will be added to the answer, because we have not counted it.

Because there are multiple sets of data, pay attention to initializing the array.

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, Q, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;
void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				++cnt;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}

int dep[MN * 2], faz[MN * 2][18], dis[MN * 2];
void DFS(int u, int fz) {
	dfn[u] = ++dfc;
	dep[u] = dep[faz[u][0] = fz] + 1;
	dis[u] = dis[fz] + (u <= N);
	for (int j = 0; j < 17; ++j)
		faz[u][j + 1] = faz[faz[u][j]][j];
	for (auto v : T[u]) if (v != fz) DFS(v, u);
}
int LCA(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int j = 0, d = dep[x] - dep[y]; d; ++j, d >>= 1)
		if (d & 1) x = faz[x][j];
	if (x == y) return x;
	for (int j = 17; ~j; --j)
		if (faz[x][j] != faz[y][j])
			x = faz[x][j], y = faz[y][j];
	return faz[x][0];
}

int main() {
	int Ti; scanf("%d", &Ti);
	while (Ti--) {
		scanf("%d%d", &N, &M);
		for (int i = 1; i <= N; ++i) {
			G[i].clear();
			dfn[i] = low[i] = 0;
		}
		for (int i = 1; i <= N * 2; ++i) T[i].clear();
		for (int i = 1, x, y; i <= M; ++i) {
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		cnt = N;
		dfc = 0, Tarjan(1), --tp;
		dfc = 0, DFS(1, 0);
		scanf("%d", &Q);
		while (Q--) {
			static int S, A[MN];
			scanf("%d", &S);
			int Ans = -2 * S;
			for (int i = 1; i <= S; ++i) scanf("%d", &A[i]);
			std::sort(A + 1, A + S + 1, [](int i, int j) { return dfn[i] < dfn[j]; });
			for (int i = 1; i <= S; ++i) {
				int u = A[i], v = A[i % S + 1];
				Ans += dis[u] + dis[v] - 2 * dis[LCA(u, v)];
			}
			if (LCA(A[1], A[S]) <= N) Ans += 2;
			printf("%d\n", Ans / 2);
		}
	}
	return 0;
}

Tags: less network REST

Posted on Fri, 05 Jun 2020 21:39:22 -0700 by OnePlus