边分治 学习笔记
就普遍理性而论,边分治能做的点分治也能做,可是难度…
参考博客:边分治讲解
前置:多叉树转二叉树
也叫三度化。
边分治在二叉树上表现得很优秀,是 \(O(nlogn)\),而在菊花图上,因为分割不均等等问题会被卡到 \(O(n^2)\)。所以,多叉树转二叉树在此显得尤为重要。
法一
算法流程:
- 若一个点有两个以上的儿子,新建两个点,并向其连边(边权为 \(0\))。
- 然后该点原来的儿子暂且归为这两个儿子,重复第一步。
- 直到他只有有两个及以下的儿子,向所有儿子连边。
Tip:均分时可以按照奇偶分类。
void pre(int u, int f) {//无向图预处理求父亲
fa[u] = f;
for (int v : g[u])
if (v != f)
pre(v, u);
}
void reBuild() {
pre(1, 0);
for (int u = 1; u <= n; ++u) {
if ((int)g[u].size() - (fa[u] != 0) <= 2) {//真实儿子数量
for(int i = 0; i < (int)g[u].size(); ++i)
if (g[u][i] != fa[u])
add(u, g[u][i], w[u][i]),
add(g[u][i], u, w[u][i]);
}
else{
int ls = ++n,rs = ++n;
val[ls] = val[rs] = val[u];
add(u, ls, 0); add(ls, u, 0);
add(u, rs, 0); add(rs, u, 0);
for (int i = 0;i < (int)g[u].size(); ++i) {
if (g[u][i] == fa[u]) swap(ls, rs);
else g[i & 1 ? ls : rs].push_back(g[u][i]);
}
}
}
}
注意:这种方法需要预处理出父亲信息,并在访问到时特殊判断。详见代码中的 pre 函数。
法二
算法流程:
- 对于一个点 \(x\),记录一个 \(last\)(初始为 \(x\))。
- 将 \(last\) 向下一个子节点连边(初始时为第一个)。
- 新建节点 \(p\),将 \(last\) 向 \(p\) 连边(边权为 \(0\))。
- 将 \(last\) 改为 \(p\)。重复步骤 \(2\),直到建完所有儿子。
void reBuild(int u, int fa) {
int las = u, p, lim = g[u].size() - (fa != 0);
for (int i = 0; i < (int)g[u][i]; ++i) {
int v = g[u][i];
if(v != fa) {
add(las, v, d[u][i]);
add(v, las, d[u][i]);
if (i < lim-1) {
p = ++n;
add(las, p, 0);
add(p, las, 0);
las = p;
}
}
else ++lim;
}
for (int v : g[u])
if(v != fa)
reBuild(v,u);
}
提供 @yanchengzhi 大佬的写法
void dfs1(int u, int from) {
bool flag = 0;
for(edge1 i : e1[u]) {
int v = i.v; ll w = i.w;
if(v == from) continue;
cur++;
add(cur, v, w);
add(v, cur, w);
if(flag) {
add(cur, cur - 1, 0);
add(cur - 1, cur, 0);
}
else {
add(cur, u, 0);
add(u, cur, 0);
}
flag = 1;
}
for(edge1 i : e1[u]) {
int v = i.v;
if(v == from) continue;
dfs1(v, u);
}
}
时空复杂度
可以证明,上述办法时空均为 \(O(n)\),不过空间需要开大一点,一般为 \(2\) 倍左右,可适当开大(稳一点建议开 \(4\) 倍)。
边分治
算法流程
类似于点分治的思想,边分治也是对于每一个点求出其两端的最大子树大小,并取最小的作为分治中心。
void getG(int u, int e, int all) {
sz[u] = 1;
for (int i = fi[u]; i; i = nxt[i])
if ((i >> 1) != e && !vis[i >> 1]) {
int v = to[i];
getG(v, i >> 1, all);
sz[u] += sz[v];
}
if (e) maxp[e] = max(sz[u], all - sz[u]);
if (maxp[e] < maxp[G])
G = e;
}
解释:\(e\) 是进入该点 \(u\) 时访问的边,\(all\) 是当前分治区域的点数。
细节注意
- 建图时一般是要在新图上开双向边。
- 建图时下标从 \(2\) 开始,因为这样可以快速访问一条边的两个端点,具体而言,一条边 \(i\) 的两个端点分别为:\(to[i],to[i\oplus 1]\)(其中 \(\oplus\) 代表按位异或)。
- 建图时,某些边权值应该设成 \(0\),或者时无穷小之类的不会影响答案的值。