Divide and conquer study notes

Introduction

Divide by point, as the name suggests, is to use the idea of ​​divide and conquer to reduce the original operation of \(n^3\) to \(\Theta (n^2\times log_n)\), which greatly improves the superiority (who does not improve efficiency? learn, hey)

The basic idea

Point divide and conquer is the same as ordinary divide and conquer. Ordinary divide and conquer is to deal with two situations: the task in one interval is transformed into the task of two intervals, the task in two sub-intervals is operated in two sub-intervals, and the tasks in two sub-intervals are operated in two sub-intervals. The tasks of the two sub-intervals are processed this time, which can improve efficiency. Extending to the tree, for the path to be found (note that it is not an edge), the path can pass through the current root node, or pass through the current root node, and process the path that does not pass through the current root node in its own subtree, and Dispose of the current root node at this time, because the depth of the tree is limited to improve efficiency, it is necessary to find a node to make the size of its own sub-tree balanced. This node is called the center of gravity of the tree. By constantly finding the center of gravity of the tree to ensure the excellence of time efficiency, if the center of gravity is not found, the tree will become a chain, and the point division (can this thing still be called divide and conquer?) will become a violent complexity.

Example Tree

Given a tree, the edges on the tree have weights, and given a threshold k, count the number of paths in the tree whose total length is less than or equal to k. The path length is the sum of the weights of all the edges on the path.

frame

This is a very classic topic in point divide and conquer. First, write the overall code of point divide and conquer:

void DFS (int u) {
	ans += Calc(u, 0);//Find the number of all solutions passing through the u node
	vis[u] = true;//said to have visited
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (vis[v]) continue;
		ans -= Calc (v, edge[i].val);//Since there may be two points in the same subtree that satisfy the condition, it is necessary to deduplicate
		root = 0;//refocus
      		Tsiz = siz[v];//Indicates the size of the current subtree
		getroot(v, u);//find the center of gravity
		DFS(root);//Divide and conquer, dealing with problems in each subtree
	}
}

It doesn't matter if you don't understand it now, you can read it after you understand the general structure.

find the roots

void getroot (int u, int fa) {
	siz[u] = 1, w[u] = 0;//preprocessing
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		getroot (v, u);//Recursively find size of heavy chain and tree
		siz[u] += siz[v];
		w[u] = max (w[u], siz[v]);//Find the node with the most nodes in the subtree of the current node
	}
	w[u] = max(w[u], Tsiz - siz[u]);//The root node has other subtrees
      	if (w[u] < w[root]) root = u;
}

The w array refers to the value with the largest size in all the subtrees under the root node, and if one node is used as the follower node, then the other points in the tree are the subtrees of the root node, find a point to make each node The subtrees are average and the root is found.

number of plans

After finding a tree root, using this root node as the starting point, there is dfs to find the number of solutions in the subtree. The sum of the distances between the two points and the root node is less than k, which satisfies the requirement. At the same time, if the two nodes are at the root In the same subtree of the node, there will be illegal schemes, and then we only need to subtract the number of redundant schemes in each subtree.

void dfs (int u, int fa, int dis) {
	a[++cnt] = dis;//push the distance of each node into the array a
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		dfs (v, u, dis + edge[i].val);//Recursive processing
	}
}
int Calc (int u, int dis) {
	cnt = 0;
	dfs (u, 0, dis);//Number of schemes in preprocessing subtree
	sort (a + 1, a + 1 + cnt);//After sorting, it can be found that it can be maintained with double pointers, and the efficiency will be greatly reduced if double pointers are not used. .
	int sum = 0;
	for (register int i = 1, j = cnt; ; i++) {
		while (j && a[i] + a[j] > k) j--;//find a valid interval
		if (j < i) break;//Prevent the same scheme from being calculated twice
		sum += j - i + 1;
	}
	return sum;
}

In the code that comes back to look at the divide and conquer,

void DFS (int u) {
      ans += Calc (u, 0);
      for (register int i = head[u]; i; i = edge[i].next) {
            ans -= Calc (v, edge[i].val);
      }
}

Note that when looking for the number of illegal solutions in the subtree, you must not find the solution in the subtree. When passing parameters to Calc, you must add the distance between the subtree and the node to u, so that the number of all solutions found is the real increase. The number of plans above, otherwise it will be reduced. You can draw a picture by yourself to understand it.

Summarize

Learning to divide and conquer is just an idea, and you need to practice more to solve some problems by using the divided and conquer.
put the overall code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
const int maxn = 4e4 + 50;
inline int read () {
	int x = 0, f = 1; char ch = getchar();
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return x * f;
}
int n, k;
int ans;
struct Edge {
	int to, next, val;
} edge[maxn << 1];
int cnt;
int tot, head[maxn];
int a[maxn];
int root;
int Tsiz;
void addedge (int a, int b, int c) {
	edge[++tot].next = head[a];
	head[a] = tot;
	edge[tot].to = b;
	edge[tot].val = c;
}
bool vis[maxn];
int siz[maxn], w[maxn];
void getroot (int u, int fa) {
	siz[u] = 1, w[u] = 0;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		getroot (v, u);
		siz[u] += siz[v];
		w[u] = max (w[u], siz[v]);
	}
	w[u] = max(w[u], Tsiz - siz[u]);
	if (w[u] < w[root]) root = u;
}
void dfs (int u, int fa, int dis) {
	a[++cnt] = dis;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		dfs (v, u, dis + edge[i].val);
	}
}
int Calc (int u, int dis) {
	cnt = 0;
	dfs (u, 0, dis);
	sort (a + 1, a + 1 + cnt);
	int sum = 0;
	for (register int i = 1, j = cnt; ; i++) {
		while (j && a[i] + a[j] > k) j--;
		if (j < i) break;
		sum += j - i + 1;
	}
	return sum;
}
void DFS (int u) {
	ans += Calc(u, 0);
	vis[u] = true;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (vis[v]) continue;
		ans -= Calc (v, edge[i].val);
		root = 0;
		Tsiz = siz[v];
		getroot(v, u);
		DFS(root);
	}
}
int main () {
	n = read();
	int x, y, z;
	for (register int i = 1; i <= n - 1; i ++) {
		x = read(), y = read(), z = read();
		addedge (x, y, z), addedge (y, x, z);
	}
	cin >> k;
	w[0] = 0x3f3f3f3f;
	root = 0;
	getroot (1, 0);
	Tsiz = n;
	DFS (root);
	printf ("%d\n", ans - n);//Note that since the follow node is also added to the a array every time dfs maintains dis, each point is also counted once more, so subtracting n is the correct answer.
	return 0;
}

Finish scattered flowers qwq

Posted by ramu_rp2005 on Sat, 14 May 2022 18:43:33 +0300