自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:15:33，当前版本为作者最后更新于2021-11-03 16:33:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

*I. P5912 [POI2004]JAS

摘自 贪心专题 第三部分例题 I.

究极神仙题。

首先对问题进行转化：相当于我们需要求原树最浅的一个点分树深度。假设点 $i$ 在倒数第 $d_i+1$ 次被问到，那么任意两个 $d$ 值相同的点 $u,v$ 之间的简单路径必然存在一个点 $a$ 使得 $d_a>d_u$，因为这样才能使它们进入不同的点分树子树，说人话即 $a$ 是深度相同的点 $u,v$ 在点分树上的 LCA（的祖先）。

考虑这样一个贪心：我们记 $S_i$ 表示 $i$ 的子树内所有可能不满足条件的 $d$ 值，即存在 $u\in \mathrm{subtree}(i)$ 使得不存在 $v\in \mathrm{path}(u,i)$ 满足 $d_v>d_u$ 的所有 $d_u$ 的集合，以二进制状压形式存储。合并 $i$ 的两个子树 $u,v$ 时，首先 $d_i$ 应大于任何一个既在 $S_u$ 又在 $S_v$ 内的元素，否则显然不合法。此外，$d_i$ 还不应存在于 $S_u$ 和 $S_v$ 中，我们选择所有满足条件的最小的 $d_i$ 即可。$S_i$ 即所有 $S_u$ 与 $\{d_i\}$ 的并去掉所有 $<d_i$ 的元素后的集合。

$$d_i=\min \{c\mid c>\max\{x\mid x\in S_u\cap S_v\}\land c\notin S_u\}\\ S_i=\{d_i\}\cup\left\{x\left|\ x\geq d_i\land x\in\bigcup_{u\in\mathrm{son}(i)}S_u\right.\right\} $$

根据点分树的结论答案不可能超过 $\log n$，因此时间复杂度 $\mathcal{O}(n\log n)$，可以做到线性：通过位运算我们求出可行的 $d_i$ 集合，取 $\mathrm{lowbit}$ 即可，拿到了最优解。

const int N = 5e4 + 5;
const int K = 1 << 16; 
int cnt, hd[N], nxt[N << 1], to[N << 1];
void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
int n, f[N], S[N], lg[K], buc[K];
void dfs(int id, int fa) {
	int msk = 0, ban = 0, leaf = 1;
	for(int i = hd[id]; i; i = nxt[i]) {
		int it = to[i];
		if(it == fa) continue;
		leaf = 0, dfs(it, id), f[id] = max(f[id], f[it]);
		msk |= ban & S[it], ban |= S[it];
	} if(leaf) return S[id] = 1, void();
	msk = (K - (1 << lg[msk])) & (K - 1 - ban);
	int c = !msk ? lg[n] + 1 : buc[msk & -msk];
	f[id] = max(f[id], c);
	S[id] = (ban & (K - (1 << c))) | (1 << c);
}

int main(){
	cin >> n;
	for(int i = 2; i < K; i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i < 16; i++) buc[1 << i] = i;
	for(int i = 1; i < n; i++) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	} dfs(1, 0), cout << f[1] << endl;
	return 0;
}

启示：遇到无从下手的问题时先尝试抽象问题并分析性质（本题中是两点间的简单路径必然存在点分树的 LCA）使其更好理解。树上问题先从叶子开始，可以先考虑一些简单情况再尝试总结策略。树形 DP 先考虑仅合并两个子树的情况。