具有 n 个顶点和 n 个查询的动态加权树

Question

您将获得一棵加权树 𝑇 = (𝑉 , 𝐸)，其中 𝑛 顶点作为输入。每条边 {𝑢, v} ∈ 𝐸 有 长度𝑙(𝑢, v)。长度也作为输入的一部分给出。然后你会被要求表演𝑛 运营。每个操作都采用以下形式之一：

•change(𝑢, v, 𝑥)：将从顶点 𝑢 到顶点 v 的边的长度更改为 𝑥。

• dist(𝑢, v)：求出 𝑇 中顶点 𝑢 到顶点 v 的距离。您应该输出这个距离作为响应。

将上述操作作为输入，

1. 提供一个总运行时间为O(n^{1.75})的算法
2. 提供一个几乎线性运行时间的算法，即如果你的算法的运行时间是 𝑇 (𝑛)，对于每个 𝜀 > 0
，我们必须有 O(n^{1+𝜀 })

我计划使用最低共同祖先（LCA）算法。

我存储从根到每个节点的距离。

预处理需要 O(n log n)

dist(u,v) 可以使用 LCA 在 O(log n) 内完成

但是对于每个顶点只有一个子节点的线性树，变化（u，v，x）的最坏情况是 O（n），因为如果连接到根的边发生变化，我需要更新所有节点的距离。

如何提高change(u,v,x)的运行时间

Answer 1

我认为阿米尔教授了“懒惰”技术，也教授了摊销分析。我认为我们可以使用一些这样的技术。

Answer 2

https://cp-algorithms.com/graph/hld.html 阿米尔真是个巨魔..............