自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 22:56:31，当前版本为作者最后更新于2025-08-16 14:41:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么只有我是大力做法？

首先在 01-Trie 上考虑，操作就是让一个人往子树里走，需要使得任意两个人不存在祖先后代的关系。

对于点 $u$ 上的人，先保证 $u$ 子树内的其它点都已经合法，那么其余所有人都在叶子上，那么 $u$ 有两种移动方案：

1. 找到子树内一个度数为 $1$ 的点 $v$ 并成为它的儿子，花费 $\text{dep}_v-\text{dep}_u+1$；
2. 找到子树内一个叶节点 $v$，此时上面一定有人，把这个人和 $u$ 上的那个人移到 $v$ 的左右儿子上面去，花费 $\text{dep}_v-\text{dep}_u+2$。

容易发现直接贪心地选择花费较少的 $v$ 是正确的，因为留给祖先用并不会使得答案变优，现在问题就在于如何动态维护如上两种点的信息。

把树拍成 dfs 序，使用线段树维护子树内深度最小的一度点和叶节点及其编号，寻找 $v$ 的时候直接在线段树上面区间查即可。

当发生修改时，会插入一些新的节点，直接维护编号是不可行的，但发现新插入的节点形成的子树内一定只有二度点和叶节点，因此对于每个点 $u$，使用小根堆 $Q_u$ 来维护 $u$ 的新插入的儿子子树中每个可用的叶节点的深度。对于每个叶节点，初始时 $Q_u$ 中仅包含 $\text{dep}_u$ 一个元素；对于非叶节点，初始时 $Q_u$ 为空。

当使用一度点 $v$ 时，将 $v$ 从一度点中移除，并往 $Q_v$ 中插入 $\text{dep}_v+1$；当使用二度点 $v$ 时，实际上使用的是 $Q_v$ 中深度最小的点，设其深度为 $d$，则将 $d$ 弹出，再插入两个 $d+1$。在对 $Q$ 做修改时，同时修改线段树上对应节点的信息。时间复杂度为 $\mathcal O(m\log n)$。

一个点上可能有很多个人，逐个处理即可。注意叶节点要特判，设有 $k$ 个人，那么只有 $k-1$ 个人需要进行如上步骤。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, INF = 1e9;
int n, m, ch[N][2], deg[N], cnt[N], tot = -1, dfn[N], nfd[N], dep[N], mxd[N], ans;
char s[N]; priority_queue<int, vector<int>, greater<int> > Q[N];
void ins() {
	int p = 0;
	for (int i = 0; s[i]; i++) {
		int c = s[i] - '0';
		if (!ch[p][c]) ch[p][c] = ++m, deg[p]++;
		p = ch[p][c];
	}
	cnt[p]++;
}
void dfs(int u, int d) {
	nfd[dfn[u] = ++tot] = u, dep[u] = d;
	for (int i : {0, 1}) if (ch[u][i]) dfs(ch[u][i], d + 1);
	mxd[u] = tot;
	if (!deg[u]) Q[u].push(dep[u]);
}
struct node { int p0, d0, p1, d1; } t[N << 2];
node operator+(node a, node b) {
	if (b.d0 < a.d0) a.p0 = b.p0, a.d0 = b.d0;
	if (b.d1 < a.d1) a.p1 = b.p1, a.d1 = b.d1;
	return a;
}
void build(int p, int l, int r) {
	if (l == r) {
		if (!deg[nfd[l]]) t[p].p0 = l, t[p].d0 = dep[nfd[l]];
		else t[p].p0 = -1, t[p].d0 = INF;
		if (deg[nfd[l]] == 1) t[p].p1 = l, t[p].d1 = dep[nfd[l]];
		else t[p].p1 = -1, t[p].d1 = INF;
		return;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	t[p] = t[p << 1] + t[p << 1 | 1];
}
node qry(int p, int l, int r, int L, int R) {
	if (L <= l && r <= R) return t[p];
	int mid = l + r >> 1;
	if (R <= mid) return qry(p << 1, l, mid, L, R);
	if (L > mid) return qry(p << 1 | 1, mid + 1, r, L, R);
	return qry(p << 1, l, mid, L, R) + qry(p << 1 | 1, mid + 1, r, L, R);
}
void upd1(int p, int l, int r, int x) {
	if (l == r) {
		t[p].p0 = l, t[p].d0 = dep[nfd[l]] + 1;
		t[p].p1 = -1, t[p].d1 = INF;
		Q[nfd[l]].push(dep[nfd[l]] + 1);
		return;
	}
	int mid = l + r >> 1;
	x <= mid ? upd1(p << 1, l, mid, x) : upd1(p << 1 | 1, mid + 1, r, x);
	t[p] = t[p << 1] + t[p << 1 | 1];
}
void upd0(int p, int l, int r, int x) {
	if (l == r) {
		int i = nfd[l], d = Q[i].top(); Q[i].pop();
		Q[i].push(d + 1), Q[i].push(d + 1);
		return t[p].d0 = Q[i].top(), void();
	}
	int mid = l + r >> 1;
	x <= mid ? upd0(p << 1, l, mid, x) : upd0(p << 1 | 1, mid + 1, r, x);
	t[p] = t[p << 1] + t[p << 1 | 1];
}
void Dfs(int u) {
	if (!deg[u]) {
		for (int i = 2; i <= cnt[u]; i++) ans += Q[u].top() - dep[u] + 2, upd0(1, 0, m, dfn[u]);
		return;
	}
	for (int i : {0, 1}) if (ch[u][i]) Dfs(ch[u][i]);
	while (cnt[u]--) {
		node p = qry(1, 0, m, dfn[u], mxd[u]);
		if (p.d1 <= p.d0) ans += p.d1 - dep[u] + 1, upd1(1, 0, m, p.p1);
		else ans += p.d0 - dep[u] + 2, upd0(1, 0, m, p.p0);
	}
}
int main() {
	// freopen("id.in", "r", stdin), freopen("id.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s, ins();
	dfs(0, 1), build(1, 0, m), Dfs(0);
	cout << ans;
//	while (1);
}