边分治 - 洛谷保存站

与点分治类似，边分治也是用来处理树上链问题的一种方法。只不过点分治是找到重心，考虑经过重心的路径；边分治是找到“重心边”（两边子树大小的最大值最小的那条边），考虑经过这条边的路径。通常情况下用边分治解题会更好想，复杂度也与点度数无关；而点分树常常需要担心点度数的问题。

## 三度化

直接找“重心边”的复杂度是错的，可以被菊花图卡成 $O(n^2)$。所以需要进行三度化。这通常也是最难的部分之一。

有两种比较常用的方法。一种是造一条虚点链，链上每个点下面能挂个儿子（边为虚边）；另一种是线段树式写法。我目前用过的是前者。

三度化的难点在于如何处理虚点虚边的权值。常常可以将那一串虚点和当前节点看作一个点，其间的边看作点内的边，依据题意设置权值。

## 模板

```cpp
void dfs_rebuild(int cur, int faa) {
	int lst = 0;
	for (unsigned int i = 0; i < vec[cur].size(); ++i) {
		int to = vec[cur][i]; if (to == faa)	continue;
		if (!lst) {
			Addedge(cur, to, 1);
			lst = cur;
		} else {
			int nw = ++tot; val[nw] = val[cur];
			Addedge(lst, nw, 0); Addedge(nw, to, 1);
			lst = nw;
		}
		dfs_rebuild(to, cur);
	}
}

bool vis[N << 1];
int Siz, mxSiz, rte, siz[N];
void find_root(int cur, int faa) {
	siz[cur] = 1;
	for (int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to; if (to == faa || vis[i])	continue;
		find_root(to, cur); siz[cur] += siz[to];
		int v = max(siz[to], Siz - siz[to]);
		if (v < mxSiz)	mxSiz = v, rte = i;
	}
}

ll ans;
void dfs_work(int nwe) {
	vis[nwe] = vis[nwe ^ 1] = true;
	int u = e[nwe].to, v = e[nwe ^ 1].to;
	//do something
	if (siz[u] > 1) {
		Siz = siz[u], mxSiz = tot;
		find_root(u, v);
		dfs_work(rte);
	}
	if (siz[v] > 1) {
		Siz = siz[v], mxSiz = tot;
		find_root(v, u);
		dfs_work(rte);
	}
}

int main() {
  //input
	tot = n;
	dfs_rebuild(1, 0);
	Siz = tot, mxSiz = tot;//bug
	find_root(1, 0);
	dfs_work(rte);
  //output
	return 0;
}
```

## 例题

其实随便挑个点分治题几乎都能作为边分治的例题。

### [最长道路tree](https://darkbzoj.tk/problem/2870)

> 给定一棵 $n$ 个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。
>
> 其中链长度定义为链上点的个数。
>
> $n \le 50000$

（显然可以并查集+树的直径，或者点分治+树状数组）

边分治+双指针。

虚点点权设为当前点点权，虚边边权设为 0，实边边权设为 1.

### [通道](https://www.luogu.com.cn/problem/P4220)

> 给定点数均为 $n$ 的三棵树，边权非负，求：
> $$
> \max_{u,v} \{ dis_1(u,v) + dis_2(u,v) + dis_3(u,v)\}
> $$
> $1 \le n \le 10^5,0 \le w \le 10^{12}$

考虑两棵树怎么做。可以在第一棵树上边分治，然后在第二棵树上建虚树跑点带权的直径。复杂度：$O(n \log n)$。

~~于是三棵树就是边分治建虚树然后虚树上边分治再虚树~~

注意到边权非负，于是直径是可以快速合并的，于是只有两棵树的时候可以直接在第一棵树上 DFS 枚举 LCA，然后根据 $dis_1(u,v) = dep_1(u) + dep_1(v) - 2dep_1(lca)$ 将 $dep$ 转化为点权扔第二棵树上，合并第二棵树上的直径。即把“第二棵树上某点集的直径”看作一个数据结构来维护。

三棵树就可以在第一棵树上边分治，第二棵树上虚树 DFS，第三棵树上维护直径。注意由于边分治要求必须是黑点和白点之间的链，维护第三棵树的直径的时候要分别维护黑直径和白直径。可以证明最长的黑白直径一定是由黑直径端点和白直径端点组成的。

复杂度：$O(n \log^2 n)$（第三棵树上欧拉序LCA，然后瓶颈就在建虚树的 `sort` 了）

## 科技：边分树合并

我们将每次的重心边记录下来成为树形关系就形成了边分树。边分树与点分树类似，只不过还包含了一些边，类似克鲁斯卡尔重构树那样，叶子节点全为点，其余节点全为边。此外，还有一些有用的性质:

- 二叉树
- 树高为 $O(\log)$

这两个性质使得边分树能够像动态开点线段树那样进行合并。如果能保证合并前边分树的大小之和为 $O(n \log n)$，并且合并完两棵树以后就弃掉他俩，不再参与其余合并的话复杂度可以保证为 $O(n \log n)$。

### 例题：[暴力写挂](https://www.luogu.com.cn/problem/P4565)

> 给两棵树 $T,T'$，求
> $$
> depth(x) + depth(y) - (depth(LCA(x , y)) + depth′ (LCA′ (x, y)))
> $$
> $n \le 366666$

枚举 $LCA'(x,y)$，剩下的部分可以转化为 $\frac 1 {2}(d_x+d_y+dis(x,y))$，建立边分树，对于每个点 $x$ 维护到其所有祖先节点（实际上是“祖先边”）的距离加上 $d_x$。维护动态开点边分树，一开始全为一条链，然后在 DFS $T'$ 的时候顺便边分树合并一下，合并的时候顺便统计一下边分树上经过每个“边”的答案（$L + R',L'+R$）。

复杂度：$O(n \log n)$

### 关键代码

```cpp
inline void build_chain(int cur) {
	int lstp = cur, lstt = ++ttot;
	for (unsigned int _ = vec[cur].size() - 1; ~_; --_) {
		++ttot;
		son[ttot][type_dir[lstp]] = lstt;
		mxv[lstt] = vec[cur][_] + val[cur];//bug
		lstp = bianfath[lstp]; lstt = ttot;
	}
	rt[cur] = ttot;
}

int merge(int x, int y) {
	if (!x || !y)	return x^ y;
	if (son[x][0] && son[y][1]) MAX(ans, mxv[son[x][0]] + mxv[son[y][1]] - ansdel);
	if (son[x][1] && son[y][0]) MAX(ans, mxv[son[x][1]] + mxv[son[y][0]] - ansdel);
	son[x][0] = merge(son[x][0], son[y][0]);
	son[x][1] = merge(son[x][1], son[y][1]);
	MAX(mxv[x], mxv[y]);
	return x;
}

void dfs_on_tree2(int cur, int faa, ll nwd) {
	MAX(ans,(val[cur] - nwd) * 2);
	build_chain(cur);
	for (unsigned int _ = 0; _ < ve[cur].size(); ++_) {
		int to = ve[cur][_], w = v[cur][_];
		if (to == faa)	continue;
		dfs_on_tree2(to, cur, nwd + w);
		ansdel = nwd << 1;
		rt[cur] = merge(rt[cur], rt[to]);//bug
	}
}
```

## 科技：可持久化边分树

既然边分树和线段树有那么多相似之处，线段树可以可持久化，边分树也应该可以可持久化。

可持久化边分树可以用来当作树上的“主席树”。

### 例题：[Can Bash Save the Day?](https://www.luogu.com.cn/problem/CF757G)

> $n$ 个点的树，边有边权。还有一个长度为 $n$ 的排列 $p_i$。两种操作：
>
> - `1 l r x`：求 $\sum_{i=l}^r dis(p_i,x)$
> - `2 x`：交换 $p_x,p_{x+1}$
>
> $1 \le n,q \le 2 \cdot 10^5$

显然点分树可以轻松解决这种问题，拿两种线段树随便维护即可。然而空间是 $O(n \log^2 n)$ 的。

还有一种树剖线段树的方法，其原理为：$ans = \sum_{i=l}^r dep_{p_i}+dep_{x}-2dep_{lca}$。标记 $p_i$ 到根的边和 $x$ 到根的边，有两种标记的边的边权和即为 $dep_{lca}$。按照 $p_i$ 建立主席树维护每条边的被覆盖次数，可以做到 $O(n \log^2 n)$ 静态。发现交换 $p_x,p_{x+1}$ 仅会影响第 $x$ 棵树，于是把它改掉即可。时空均为 $O(n \log^2 n)$

然而空间都太大了，无法通过此题。但是那个主席树的方法的那个 $\log$ 是从树链剖分那里出来的，如果我们能砍掉那个 $\log$ 就可以了。

考虑用边分树去做这道题。维护每个点到其各个边分树祖先的距离，主席（边分）树维护每个边分树节点的左右子树中到这个节点的距离和。交换操作与链剖方法一样，查询就在主席树上从到 $x$ 的链上查即可，原理同正常边分树，写法同主席树。

时空复杂度：$O(n \log n)$

### 关键代码

```cpp
void rebuild(int cur, int faa)
void find_root(int cur, int faa)
int dep[N];
ll state[N];
vector<ll> vec[N];
void dfs_dis(int cur, int faa, ll nwd, int t) {
	state[cur] |= (t << dep[cur]); ++dep[cur]; vec[cur].push_back(nwd);//bug
  //DFS
}

void dfs_tre(int nwe) {
	vis[nwe] = vis[nwe ^ 1] = true;
	int u = e[nwe].to, v = e[nwe ^ 1].to;
	dfs_dis(u, v, 0, 0), dfs_dis(v, u, e[nwe].val, 1);
	//divide and conquer
}

int son[NN][2], rt[N], ttot, jzpsiz[NN];
ll sum[NN];
void add(int p, int nwd, int s, int lstcur, int &cur) {
	cur = ++ttot; son[cur][0] = son[lstcur][0], son[cur][1] = son[lstcur][1];//BUG
	if (nwd == dep[p])	return ;
	add(p, nwd + 1, s >> 1, son[lstcur][s & 1], son[cur][s & 1]);
	int sn = son[cur][s & 1], lsn = son[lstcur][s & 1];
	sum[sn] = sum[lsn] + vec[p][nwd];
	jzpsiz[sn] = jzpsiz[lsn] + 1;
}
void modify(int p, int nwd, int s, int t, int lstcur, int &cur) {//Bug
	cur = ++ttot; son[cur][0] = son[lstcur][0], son[cur][1] = son[lstcur][1];
	if (nwd == dep[p])	return ;
	modify(p, nwd + 1, s >> 1, t, son[lstcur][s & 1], son[cur][s & 1]);
	int sn = son[cur][s & 1], lsn = son[lstcur][s & 1];
	sum[sn] = sum[lsn] + t * vec[p][nwd];
	jzpsiz[sn] = jzpsiz[lsn] + t;
}
ll query(int p, int nwd, int s, int addcur, int delcur) {
	if (nwd == dep[p])	return 0;
	int asn = son[addcur][s & 1], dsn = son[delcur][s & 1];
	ll res = query(p, nwd + 1, s >> 1, asn, dsn);
	int dedir = (s & 1) ^ 1;
	asn = son[addcur][dedir], dsn = son[delcur][dedir];
	res += (sum[asn] - sum[dsn]) + vec[p][nwd] * (jzpsiz[asn] - jzpsiz[dsn]);
	return res;
}

int p[N];
int main() {
  //input
	rebuild(1, 0);
	Siz = tot, mxSiz = tot;
	find_root(1, 0);
	dfs_tre(rte);
	for (int i = 1; i <= n; ++i)
		add(p[i], 0, state[p[i]], rt[i - 1], rt[i]);
	ll ans = 0;
	for (int i = 1; i <= q; ++i) {
    //input
		if (t == 1) {
      //input
			ans = query(x, 0, state[x], rt[r], rt[l - 1]);
      //output
		} else {
      //input
			modify(p[x], 0, state[p[x]], -1, rt[x], rt[x]);
			swap(p[x], p[x + 1]);
			modify(p[x], 0, state[p[x]], 1, rt[x], rt[x]);
		}
	}
	return 0;
}
```

正在渲染内容...