如何回答DAG上最长体重路径上的单节点编辑查询

Question

在形式上，我们给出了一个图G，其中'n'个节点上都有+ ve个数字。我们被赋予了没有循环的有向边。那么我们被要求回答Q查询，每个查询要求编辑G上的节点权重，并且我们必须打印最长权重路径权重。请注意，每个查询意味着从原始图形编辑单个节点。 N < = 10^5 & Q < = 10^6。什么是最具时间效益的解决方案？

Ofcourse bruteforce将采取太多的O（n q）。我尝试了2,3种不同的bruteforce，它可以提供更好的平均时间复杂度，但是我可以找到每个解决方案的至少一个测试数据，如果我们反复询问就像O（n q）一样差。

Answer 1

要回答每个O（1）次的查询，只需知道每个节点使用/不使用该节点的最重路径的权重，因为这些类中的路径权重会受到影响通过改变节点的重量。通过例如为每个节点计算该节点是源/汇的最重路径的权重，在O（n）时间中直接实现“使用”一半。

“不使用”的一半是什么使这个问题变得有趣。假设节点按照拓扑顺序编号为1..n，弧从低到高。使用之前计算的数据，我们可以给定一个弧u→v，在O（1）中计算包含该弧的最重路径的权重。这样的路径肯定会跳过节点u + 1..v-1，因此我们可以相应地更新这些节点的“不使用”最大值。如果我们对所有弧进行此操作，包括一些来自哨兵源0（权重为0到1..n）的哨兵弧到砝码为0的哨兵宿n + 1，则我们得到正确的“不使用”值。

现在，以明显的方式做这件事太慢了：O（mn）预处理的时间总共为O（mn + q），其中m是弧的数量，n是节点的数量，q是查询的数量。分段树将预处理时间缩短为O（m log n）。