修改后的树路径查询
Queries on Tree Path with Modifications
问题：
给你一棵树，有 n 个节点（可以是 最多 10^5）和 n-1双向边。假设每个节点包含两个值：
- 它是索引（只是节点的唯一编号），假设它将是从 1 到 n。
- 它的值是 Vi，可以从 1 到 10^8
现在同一棵树上会有多个相同类型的查询（查询数量最多可达10^5），如下：
- 给定节点 1、节点 2 和值 P（可以从 1 到 10^8）。
并且对于每个此类查询，您只需找到从 node1 到 node2 的路径中的节点数，其值 小于 P.
注意：所有节点之间的路径都是唯一的，没有两条边属于同一对节点。
所需的时间复杂度 O(nLog(n)) 或者可以用其他术语表示，但在给定的约束条件下应该可以在 1 秒内解决。
我尝试过的：
(A)。如果 P 的值固定，我可以很容易地解决它，使用 O(nLog(n)) 中的 LCA 方法通过在每个节点存储以下信息：
- 从根节点到给定节点的值小于 P 的节点数。
但是这里的 P 变化太大，所以这无济于事。
(乙)。我在想的其他方法是使用简单的 DFS。但这也需要 O(nq)，其中 q 是查询的数量。同样，因为 n 和 q 都在 1 到 10^5 之间变化，所以这在给定的时间限制下也无济于事。
我想不出别的了。任何帮助，将不胜感激。 :)
来源：
我猜我在 SPOJ 的某个地方读到了这个问题。但是现在找不到了。尝试在 Web 上搜索它但无法在任何地方找到解决方案（Codeforces、CodeChef、SPOJ、Whosebug）。
令ans(v, P)为从根到v的垂直路径上的答案和P的给定值。
我们如何计算呢？有一个简单的离线解决方案：我们可以将给定节点的所有查询存储在与其关联的向量中，运行 深度优先搜索将所有值保留在数据结构中路径的当前路径上，可以执行以下操作:
- 添加一个值
- 删除一个值
- 统计小于
X 的元素个数
任何平衡的二叉搜索树都可以。你可以让它更简单：如果你事先知道所有的查询，你可以压缩数字，使它们在 [0..n - 1] 范围内，并使用二叉索引树。
回到最初的问题：(u, v, P) 查询的答案显然是 ans(v, P) + ans(u, P) - 2 * ans(LCA(u, v), P)。
就是这样。时间复杂度为O((N + Q) log N).
问题：
给你一棵树，有 n 个节点（可以是 最多 10^5）和 n-1双向边。假设每个节点包含两个值：
- 它是索引（只是节点的唯一编号），假设它将是从 1 到 n。
- 它的值是 Vi，可以从 1 到 10^8
现在同一棵树上会有多个相同类型的查询（查询数量最多可达10^5），如下：
- 给定节点 1、节点 2 和值 P（可以从 1 到 10^8）。
并且对于每个此类查询，您只需找到从 node1 到 node2 的路径中的节点数，其值 小于 P.
注意：所有节点之间的路径都是唯一的，没有两条边属于同一对节点。
所需的时间复杂度 O(nLog(n)) 或者可以用其他术语表示，但在给定的约束条件下应该可以在 1 秒内解决。
我尝试过的：
(A)。如果 P 的值固定，我可以很容易地解决它，使用 O(nLog(n)) 中的 LCA 方法通过在每个节点存储以下信息：
- 从根节点到给定节点的值小于 P 的节点数。
但是这里的 P 变化太大，所以这无济于事。
(乙)。我在想的其他方法是使用简单的 DFS。但这也需要 O(nq)，其中 q 是查询的数量。同样，因为 n 和 q 都在 1 到 10^5 之间变化，所以这在给定的时间限制下也无济于事。
我想不出别的了。任何帮助，将不胜感激。 :)
来源：
我猜我在 SPOJ 的某个地方读到了这个问题。但是现在找不到了。尝试在 Web 上搜索它但无法在任何地方找到解决方案（Codeforces、CodeChef、SPOJ、Whosebug）。
令
ans(v, P)为从根到v的垂直路径上的答案和P的给定值。我们如何计算呢？有一个简单的离线解决方案：我们可以将给定节点的所有查询存储在与其关联的向量中，运行 深度优先搜索将所有值保留在数据结构中路径的当前路径上，可以执行以下操作:
- 添加一个值
- 删除一个值
- 统计小于
X的元素个数
任何平衡的二叉搜索树都可以。你可以让它更简单：如果你事先知道所有的查询，你可以压缩数字，使它们在
[0..n - 1]范围内，并使用二叉索引树。回到最初的问题：
(u, v, P)查询的答案显然是ans(v, P) + ans(u, P) - 2 * ans(LCA(u, v), P)。
就是这样。时间复杂度为O((N + Q) log N).