2

问题：

给你一棵树，它有n 个节点（最多可达 10^5）和n-1 个双向边。假设每个节点包含两个值：

  1. 它是索引（只是节点的唯一编号），可以说它是从 1 到 n。
  2. 它的值Vi，可以在1 到 10^8之间变化

现在在同一棵树上将有多个相同类型的查询（查询数可以达到 10^5），如下所示：

  1. 您将获得 node1、node2 和一个值P（可以在1 到 10^8之间变化）。

对于每一种此类查询，您只需找到从 node1 到 node2 的路径中其值小于 P的节点数。

注意：所有节点之间会有唯一的路径，并且没有两条边属于同一对节点。

所需的时间复杂度 O(nLog(n)) 或者可以用其他术语表示，但在给定的约束条件下应该可以在 1 秒内解决。

我试过的：

（一个）。如果 P 的值是固定的，我可以很容易地解决它，使用 O(nLog(n)) 中的 LCA 方法，通过在每个节点存储以下信息：

  1. 从根到给定节点的值小于 P 的节点数。

但是这里的 P 变化太大，所以这无济于事。

（乙）。我在想的其他方法是使用简单的 DFS。但这也需要 O(nq)，其中 q 是查询数。同样，因为 n 和 q 都在 1 到 10^5 之间变化，所以这在给定的时间限制下也无济于事。

我想不出别的了。任何帮助，将不胜感激。:)

资源：

我猜我在 SPOJ 的某个地方读到了这个问题。但是现在找不到了。尝试在 Web 上搜索它，但在任何地方都找不到解决方案（Codeforces、CodeChef、SPOJ、StackOverflow）。

4

1 回答 1

3

  1. 让ans(v, P)是从根到v给定值的垂直路径上的答案P。

  2. 我们如何计算它？有一个简单的离线解决方案：我们可以将给定节点的所有查询存储在与其关联的向量中，运行深度优先搜索，将当前路径上的所有值与数据结构中的路径保持一致，可以执行以下操作：

    • 添加一个值
    • 删除一个值
    • 计算小于的元素数X

    任何平衡的二叉搜索树都可以。你可以让它更简单：如果你事先知道所有的查询，你可以压缩数字，使它们在[0..n - 1]范围内并使用二叉​​索引树。

  3. 回到原来的问题：一个(u, v, P)查询的答案是明确的ans(v, P) + ans(u, P) - 2 * ans(LCA(u, v), P)。

而已。时间复杂度为O((N + Q) log N)。

于 2017-07-08T22:05:17.493 回答