3

这个问题是由 codechef 中的travtree问题引起的。在社论DFS中，他们建议通过在遍历中记录每个节点的发现和退出时间，将树线性化为数组。现在我们可以通过汇总该节点sum subtree段中发生的事件来快速回答有关- 的查询。[discovery time, exit time]（我们使用Fenwick树来快速回答这些查询）。

然而，为了解决这个问题，我们还需要快速回答sum path查询。也就是对沿最短路径发生的事件求和a, b。这怎么可能？他们给出的答案是这样的：

对于每个有趣的事件，他们都会更新：

    update(BT2,event_node,1);
    update(BT2,out[event_node],-1);

现在sum path(a,b)是这样的：

    int l = lca(a,b);
    ans = query(BT2,a) + query(BT2,b) - query(BT2,l) -  (l==1  ? 0 : query(BT2, parent[0][l]));

query前缀总和在哪里。怎么正确？？当您查看前缀总和时，您可能会遇到许多与和a之间的路径无关的节点！la

4

1 回答 1

0

为了线性化sum path查询 - 树节点之间最短路径上发生的事件总和，a, b我们确实必须执行以下操作：

当节点中发生事件时v，我们update(IN[v], 1)和update(OUT[v], -1). IN是节点的 DFSdiscovery time和OUTDFS exit time。

现在查询将是query(IN[b]) - query(IN[a]-1). 是query(IN[b])一个前缀和：它从根开始，遍历树直到它到达b。请注意，对于每个节点v，我们不会在从 root 到的直接路径上b传递，我们会发现并最终退出它。仅对于路径上的节点，我们会发现并且不会退出。由于我们更新的方式，这意味着我们将有效地求和路径上的节点root, b（包括b）。

现在很明显，同样的情况发生在query(IN[a]-1)- 它是路径上节点的总和root, a（不包括a这次）。减去它们给我们a, b。画一个草图，你会亲眼看到它。

为了完整性 - for 的方法sum subtree在 inupdate和 in 中都不同query。对于每个事件你只update(IN[v])。现在查询sum subtree(a)我们做query(OUT[a]) - query(IN[a]-1)。这一次，query(OUT[a])我们将遍历的所有节点求和，直到发现a，然后将a的子树中的所有节点求和，直到我们退出它。现在我们减去query(IN[a] - 1)所有节点，直到我们发现a。我们只剩a下子树。

于 2016-07-27T21:05:25.843 回答