P6227 [BalticOI 2019 Day1] 山谷

yangjintian · 2023-07-25 13:46:49 · 题解

原题链接

题目大意：

一颗 N 个节点的以 E 为根的树，每条边有权值 W_i，有 S 个特殊点和 Q 次询问。 每次询问第 I 条边不能经过，并给定一个起点 R。

1.若能走到根节点，则输出 escaped。

2.若走不到根节点也走不到任意个特殊点，则输出 oo。

3.若走不到根节点但能走到特殊点，则输出最近特殊点的距离。

解题思路：

先给张图，方便理解（图很丑，看懂就行 QWQ）

我们设深度大的那个点为 P。

第一种情况输出 escaped ：

那就说明 R 到 E 的路没被断开，也就是 R 不在 P 的子树内，所以 \operatorname{lca}(R , P) \ne P。

第二种情况输出 oo ：

到不了根节点且到不了特殊点，说明 R 在 P 的子树内，即 \operatorname{lca}(R , P) = P 且 P 的子树内（包含 P）没有商店。

第三种情况：

到不了根节点，但能到特殊点。

找的特殊点的范围一定在 P 的子树内,即 \operatorname{lca}(R , P) = P。

暴力 DFS 找复杂度是 O(n^2) 的，考虑优化，这种树上问题的优化很多很多都是用倍增的。

注意到 ans = \min(c[R] - c[i] + nearshop[i])。

其中 i 为 R 的祖先（包括 R）,c[i] 表示从 i 到根节点的距离，nearshop[i] 表示子树内离 i 最近的特殊点的距离。