【边分治】P4565 [CTSC2018] 暴力写挂

初涉边分治。

大致就是按照一条边的两端来分类出两套点，然后对这个进行分治，有点是只用考虑两类集合，考虑贡献很简单！！反正就是比点分强。

但是如果直接分治是假的，会被菊花图薄纱，需要进行对树的三度化，这个是左儿子右兄弟，但是貌似很少人叫这个，比较不适，然后我们就可以做了。

建出来的边分树按照这个想法就是一颗二叉树，这个题考虑式子求二分之一，然后考虑边分树合并即可。

https://blog.csdn.net/cqbzlydd/article/details/128506334 大概是这样子。我抄袭题解。

int ecnt = 1, rte, all, msz;
int hd[___], sz[___], rdp[___];
ll dep[___], prv[___];

void addedge (int x, int y, int w) {
	e[++ ecnt] = {hd[x], y, w};
	hd[x] = ecnt;
}
void dfs1 (int x, int fa) {
	for (int i = hd[x]; i; i = e[i].nxt) {
		int y = e[i].y;
		if (y == fa) continue ;
		rdp[y] = rdp[x] + 1, 
		dep[y] = dep[x] + e[i].w;
		dfs1(y, x);
	}	
}
void dfs2 (int x, int fa) {
	all ++;
	for (int i = hd[x]; i; i = e[i].nxt) {
		int y = e[i].y;
		if (e[i].vis || (y == fa)) continue ;
		dfs2(y, x);
	}
}
void findrt (int x, int fa) {
	sz[x] = 1;
	for (int i = hd[x]; i; i = e[i].nxt) {
		int y = e[i].y;
		if (e[i].vis || (y == fa)) continue ;
		findrt(y, x);
		sz[x] += sz[y];
		int cur = abs(all - 2 * sz[y]);
		if (cur < msz) msz = cur, rte = i;
	}
}
void dfs3 (int x, int fa, int dir) {
	if (x <= n) {
		int cur = ++ nd;
		val[cur] = dep[x] + prv[x];
		son[rt[x]][dir] = cur;
		rt[x] = cur;
	}
	for (int i = hd[x]; i; i = e[i].nxt) {
		int y = e[i].y;
		if (e[i].vis || (y == fa)) continue ;
		prv[y] = prv[x] + e[i].w;
		dfs3(y, x, dir);
	}
}
void solve (int x) {
	all = 0;
	dfs2(x, 0);
	if (all == 1) return ;
	msz = 1e9, findrt(x, 0);
	int u = e[rte].y, v = e[rte ^ 1].y;
	e[rte].vis = e[rte ^ 1].vis = 1;
	prv[u] = e[rte].w, prv[v] = 0;
	dfs3(u, 0, rdp[u] > rdp[v]), dfs3(v, 0, rdp[v] > rdp[u]);
	solve(u), solve(v); 
}
int merge (int x, int y) {
	if (!x || !y) return x | y;
	if (son[x][0] && son[y][1]) 
		res = max(res, val[son[x][0]] + val[son[y][1]]);
	if (son[x][1] && son[y][0])
		res = max(res, val[son[x][1]] + val[son[y][0]]);
	val[x] = max(val[x], val[y]);
	son[x][0] = merge(son[x][0], son[y][0]),
	son[x][1] = merge(son[x][1], son[y][1]);
	return x;
}
void rebuild (int x, int fa) {
	int lst = x;
	for (auto & [y, w] : tr[x]) {
		if (y == fa) continue ;
		int cur  = ++ ndc;
		t1::addedge(lst, cur, 0), t1::addedge(cur, lst, 0);
		t1::addedge(cur, y, w), t1::addedge(y, cur, w);
		rebuild(y, x);
		lst = cur;
	}
}

放出部分屎山代码供参考。

我大致讲一下 Implement 是怎么样的。考虑像点分一样找出一条归类后差小的边。然后按照原树上的深度上归类出两类点。

边分树显然就是按照一些根来归类，然后一步一步走下来的链，然后我们可以按照这个来做到一个枚举边分树上的前缀和的一个效果。

便于实现，写几点吧：

• 把 \(rt_x\) 设为 \(x\)，便于走下去。

• 都什么年代，还在写传统点分？

int cur = abs(all - 2 * sz[y]);

• 使用类似网络流的成对存储。

• 三度化写左儿子右兄弟的时候要注意虚点没有贡献的问题。