寒鸽儿のBlog

寒鸽儿gugugu~

首页 归档 标签 关于

点分治1 2020-07-21~2020-07-22

2020-07-20 15 min read # 树 # 点分治 # 训练日记 # 图论 # 笔记

view

  1. 学习点分治 , 看了 几篇课件和《进阶指南》4.5 、XD7.15《图论课1》回放以及这个
  2. 点分治板子
  3. LG4178
  4. CF161D

detail

点分治

思想

一般用于做树上路径相关的统计。
统计根的孩子中跨过根的路径 , 一般需要做到 O(n)\mathcal{O(n)} 或者 O(nlog⁡n)\mathcal{O(n \log n)} , 然后删掉根节点 , 递归统计各个子树的情况。
根选择重心可以保证优秀的复杂度。

处理方式

  1. 点分治 --> 考虑统计以根为lca的点对的情况。
  2. 处理可以把所有结点放在数组中排序然后two_pointer , 像莫队那样在移动指针的时候统计[l, r]之间的颜色数量。比较适用于求 ⩽k\leqslant k 或 ⩾k\geqslant k 的节点对。
  3. 可以使用平衡树或者权值树来统计。对每棵子树依次calc-add。 用map可以方便地求 =k=k 的节点对。

LG点分治板子

事项

  1. work()函数(点分治主过程)用递归实现的效率高于用队列+循环实现。
  2. 用树状数组处理不应用memset , 而是将栈中的点对应的位置清零。(用memset复杂度会炸)
  3. 注意two_pointer的实现方式。

Code

递归实现(12ms , 1.56MB)

#include <bits/stdc++.h>

const int maxn = 12345, maxm = 123;

struct edge {
	int x, w;
	edge() { x = w = 0; }
	edge(int x, int w) : x(x), w(w) {}
};

typedef std::vector<std::vector< edge > > Graph;

Graph G;
int qry[maxm], q;
int siz[maxn];
int stk[maxn], top, fa[maxn];
int d[maxn], col[maxn];
bool del[maxn], ans[maxn];

void dfs1(int pre, int cur) {
	stk[top++] = cur; siz[cur] = 1;
	fa[cur] = pre;
	for(edge e : G[cur])
		if(!del[e.x] && pre != e.x) {
			dfs1(cur, e.x);
			siz[cur] += siz[e.x];
		}
}

int find_root(int xx) {
	stk[0] = xx; top = 1;
	siz[xx] = 1;
	for(edge e : G[xx])
		if(!del[e.x]) {
			dfs1(xx, e.x);
			siz[xx] += siz[e.x];
		}
	for(int i = 0; i < top; ++i)
		if(top - siz[stk[i]] <= (top >> 1)) {
			bool flg = true;
			for(edge e : G[stk[i]])
				if(!del[e.x] && e.x != fa[stk[i]] && siz[e.x] > (top >> 1)) {
					flg = false;
					break;
				}
			if(flg) return stk[i];
		}
}

void dfs2(int pre, int cur, int w, int color) {
	d[cur] = d[pre] + w;
	col[cur] = color;
	for(edge e : G[cur])
		if(!del[e.x] && e.x != pre)
			dfs2(cur, e.x, e.w, color);
}

void work(int xx) {
	int rt = find_root(xx);
	if(top == 1) return;
	d[rt] = 0; col[rt] = 0;
	for(edge e : G[rt])
	 	if(!del[e.x])
			dfs2(rt, e.x, e.w, e.x);
	std::sort(stk, stk + top, [&](int x, int y){ return d[x] < d[y]; });
	for(int i = 0; i < q; ++i) {
		if(ans[i]) continue;
		int l = 0, r = top - 1;
		while(l < r) {
			if(d[stk[l]] + d[stk[r]] < qry[i]) ++l;
			else if(d[stk[l]] + d[stk[r]] > qry[i]) --r;
			else if(d[stk[l]] + d[stk[r]] == qry[i]) {
				if(col[stk[l]] != col[stk[r]]) {
					ans[i] = true;
					break;
				}
				if(d[stk[l + 1]] == d[stk[l]]) ++l;
				else --r;
			}
		}
	}
	del[rt] = true;
	for(edge e : G[rt])
		if(!del[e.x])
			work(e.x);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	memset(del, false, sizeof(del));
	int n, u, v, w;
	std::cin >> n >> q;
	G.resize(n + 1);
	for(int i = 1; i < n; ++i) {
		std::cin >> u >> v >> w;
		G[u].push_back(edge(v, w));
		G[v].push_back(edge(u, w));
	}
	for(int i = 0; i < q; ++i) std::cin >> qry[i];
	work(1);
	for(int i = 0; i < q; ++i)
		if(ans[i])
			std::cout << "AYE\n";
		else
			std::cout << "NAY\n";
	return 0;
}

队列 + 循环实现(32ms , 2.18MB)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 12345, maxm = 123;

struct edge {
	int x, w;
	edge() {}
	edge(int x, int w) : x(x), w(w) {} 
};
typedef vector< vector<edge> > graph;

graph G;
queue<int> q;
int qry[maxm], m;
int stk[maxn], top;
int siz[maxn], fa[maxn];
int d[maxn], col[maxn], ans[maxn];
bool del[maxn];

void dfs1(int pre, int cur) {
	stk[top++] = cur;
	siz[cur] = 1; fa[cur] = pre;
	for(edge e : G[cur])
		if(!del[e.x] && e.x != pre)	 {
			dfs1(cur, e.x);
			siz[cur] += siz[e.x];
		}
}

int findroot(int xx) {
	top = 1;
	stk[0] = xx;
	siz[xx] = 1;
	for(edge e : G[xx]) 
		if(!del[e.x]) {
			dfs1(xx, e.x);
			siz[xx] += siz[e.x];
		}
	if(top == 1) return xx;
	for(int i = 0; i < top; ++i) {
		int cur = stk[i];
		if(top - siz[cur] > top / 2) continue;
		bool flg = true;
		for(edge e : G[cur]) 
			if(!del[e.x] && e.x != fa[cur] && siz[e.x] > top / 2) {
				flg = false;
				break;
			}
		if(flg) return cur;
	}
}

void dfs2(int pre, int cur, int w, int color) {
	col[cur] = color;
	d[cur] = d[pre] + w;
	for(edge e : G[cur])
		if(!del[e.x] && e.x != pre)
			dfs2(cur, e.x, e.w, color);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, u, v, w;
	cin >> n >> m;
	G.resize(n + 1);
	for(int i = 1; i < n; ++i) {
		cin >> u >> v >> w;
		G[u].push_back(edge(v, w));
		G[v].push_back(edge(u, w));
	}
	for(int i = 1; i <= m; ++i) cin >> qry[i];
	q.push(1);
	while(!q.empty()) {
		int xx = q.front(); q.pop();
		int root = findroot(xx);
		if(top == 1) continue;
		d[root] = col[root] = 0;
		for(edge e : G[root])
			if(!del[e.x])
				dfs2(root, e.x, e.w, e.x);
		sort(stk, stk + top, [&](int x, int y){ return d[x] < d[y]; });
		for(int i = 1; i <= m; ++i) {
			if(ans[i]) continue;
			int l = 0, r = top - 1; 
			while(l < r) {
				if(d[stk[l]] + d[stk[r]] < qry[i]) ++l;
				else if(d[stk[l]] + d[stk[r]] > qry[i]) --r;
				else if(col[stk[l]] == col[stk[r]]) {
					if(d[stk[l]] == d[stk[l + 1]]) ++l;
					else --r;
				} else {
					ans[i] = true;
					break;
				}
			}
		}
		del[root] = true;
		for(edge e : G[root])
			if(!del[e.x])
				q.push(e.x);
	}
	for(int i = 1; i <= m; ++i)
	if(ans[i])
		std::cout << "AYE\n";
	else
		std::cout << "NAY\n";
	return 0;	
}

LG4178

事项

  1. 可用two_pointer解决 , 比较方便地求出点对数目(R-L-num[col[L]])。

code

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define itra std::vector<int>::iterator;
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

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

const int maxn = 56789;

struct edge {
	int x, w;
	edge() {}
	edge(int x, int w) : x(x), w(w) {}
};

typedef vector< vector<edge> > graph;
graph G;
long long ans = 0;
int k;
int stk[maxn], top;
int siz[maxn], fa[maxn];
int dis[maxn], col[maxn];
bool del[maxn];
int num[maxn];


void dfs1(int pre, int cur) {
	siz[cur] = 1; fa[cur] = pre;
	stk[top++] = cur;
	for(edge e : G[cur])
		if(e.x != pre && !del[e.x]) {
			dfs1(cur, e.x);
			siz[cur] += siz[e.x];
		}
}

int findroot(int xx) {
	stk[0] = xx; top = 1;
	siz[xx] = 1;
	for(edge e : G[xx]) 
		if(!del[e.x]) {
			dfs1(xx, e.x);
			siz[xx] += siz[e.x];
		}
	for(int i = 0; i < top; ++i) {
		int cur = stk[i];
		if(top - siz[cur] > top / 2) continue;
		bool flg = true;
		for(edge e : G[cur])	
			if(!del[e.x] && e.x != fa[cur] && siz[e.x] > top / 2) {
				flg = false; break;
			}
		if(flg) return cur;
	}
}

void dfs2(int pre, int cur, int wei, int color) {
	dis[cur] = dis[pre] + wei;
	col[cur] = color;
	for(edge e : G[cur])
		if(!del[e.x] && e.x != pre)
			dfs2(cur, e.x, e.w, color);
}

long long calc(int k) {
	long long ans = 0;
	int l = 0, r = top - 1;
	for(int i = 1; i < top; ++i) ++num[col[stk[i]]];
	for(; l < r; --num[col[stk[++l]]]) {
		while(dis[stk[r]] + dis[stk[l]] > k) {
			--num[col[stk[r]]]; --r;
		}
		if(r > l)
			ans += r - l - num[col[stk[l]]];
	}
	for(int i = 0; i < top; ++i) num[col[stk[i]]] = 0;
	return ans;
}

void work(int xx) {
	xx = findroot(xx);
	if(top == 1) return;
	col[xx] = dis[xx] = 0;
	for(edge e : G[xx])
		if(!del[e.x])
			dfs2(xx, e.x, e.w, e.x);
	sort(stk, stk + top, [&](int x, int y){ return dis[x] < dis[y]; });
	ans += calc(k);
	del[xx] = true;
	for(edge e : G[xx])
		if(!del[e.x])
			work(e.x);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, u, v, w;
	cin >> n;
	G.resize(n + 1);
	repp(i,1,n) {
		cin >> u >> v >> w;
		G[u].push_back(edge(v, w));
		G[v].push_back(edge(u, w));
	}
	cin >> k;
	work(1);
	cout << ans << endl;
	return 0;
}

CF161D

事项

  1. two_pointer法直接解决 =k=k 过程中会有很大的分类讨论麻烦。为减轻代码难度可适当牺牲常数 : 实现calc(k)统计 ⩽k\leqslant k , 用calc(k) - calc(k-1)求 =k=k 。
  2. 可用map , 对每棵子树calc-add。然后启发式合并。(没实现过)
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define itra std::vector<int>::iterator;
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

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

const int maxn = 56789;

typedef vector< vector<int> > graph;
graph G;
long long ans = 0;
int k;
int stk[maxn], top;
int siz[maxn], fa[maxn];
int dis[maxn], col[maxn];
bool del[maxn];
int num[maxn];


void dfs1(int pre, int cur) {
	siz[cur] = 1; fa[cur] = pre;
	stk[top++] = cur;
	for(int ver : G[cur])
		if(ver != pre && !del[ver]) {
			dfs1(cur, ver);
			siz[cur] += siz[ver];
		}
}

int findroot(int xx) {
	stk[0] = xx; top = 1;
	siz[xx] = 1;
	for(int ver : G[xx]) 
		if(!del[ver]) {
			dfs1(xx, ver);
			siz[xx] += siz[ver];
		}
	for(int i = 0; i < top; ++i) {
		int cur = stk[i];
		if(top - siz[cur] > top / 2) continue;
		bool flg = true;
		for(int ver : G[cur])	
			if(!del[ver] && ver != fa[cur] && siz[ver] > top / 2) {
				flg = false; break;
			}
		if(flg) return cur;
	}
}

void dfs2(int pre, int cur, int color) {
	dis[cur] = dis[pre] + 1;
	col[cur] = color;
	for(int ver : G[cur])
		if(!del[ver] && ver != pre)
			dfs2(cur, ver, color);
}

long long calc(int k) {
	long long ans = 0;
	int l = 0, r = top - 1;
	for(int i = 1; i < top; ++i) ++num[col[stk[i]]];
	for(; l < r; --num[col[stk[++l]]]) {
		while(dis[stk[r]] + dis[stk[l]] > k) {
			--num[col[stk[r]]]; --r;
		}
		if(r > l)
			ans += r - l - num[col[stk[l]]];
	}
	for(int i = 0; i < top; ++i) num[col[stk[i]]] = 0;
	return ans;
}

void work(int xx) {
	xx = findroot(xx);
	if(top == 1) return;
	col[xx] = dis[xx] = 0;
	for(int ver : G[xx])
		if(!del[ver])
			dfs2(xx, ver, ver);
	sort(stk, stk + top, [&](int x, int y){ return dis[x] < dis[y]; });
	ans += calc(k) - calc(k-1);
	del[xx] = true;
	for(int ver : G[xx])
		if(!del[ver])
			work(ver);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, u, v;
	cin >> n >> k;
	G.resize(n + 1);
	repp(i,1,n) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	work(1);
	cout << ans << endl;
	return 0;
}
Powered by Gridea RSS