这个问题是由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是前缀总和。这是怎么回事？？当您查看前缀 sum 直到 a 时，您可能会遇到许多与 l 和 a 之间的路径无关的节点！
为了线性化sum path查询 - 树节点之间最短路径上发生的事件总和 a, b 我们确实必须执行以下操作：
当节点v发生事件时，我们update(IN[v], 1)并update(OUT[v], -1)。 IN是节点的 DFS discovery time，OUT DFS exit time 。
现在查询将query(IN[b]) - query(IN[a]-1)。query(IN[b])是一个前缀总和：它从根开始，遍历树，直到到达b。请注意，对于每个节点v我们将不传递从根到b的直接路径，我们将发现并最终退出它。仅对于我们将发现的路径上的节点，而不是退出。由于我们更新的方式，这意味着我们将有效地对路径root, b上的节点求和(包括b(。
现在很明显，同样的情况发生在query(IN[a]-1)中 - 它是路径root, a上节点的总和(这次不包括a(。减去它们会给我们带来a, b.画一张草图，你就会亲眼看到它。
为了完整性 - sum subtree的方法在update和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子树。