给你一棵有 n 个顶点的树。每个节点都有一个与之关联的整数权重。 给定树上有大量查询(~n^2)。 对于查询(A，B)，其中A，B是树的两个顶点，您需要计算从A到B的唯一路径上的节点的权重之和，包括A和B。
我可以为单个查询执行 dfs/bfs，但这将花费 O(n^3) 来处理 ~n^2 可能的查询.. 任何人都可以提出更好的建议，每个查询花费的时间少于 O(n) 吗？
谢谢..
最佳答案
如果树没有根，则使任意节点成为树的根。
我们将用 W[x] 表示节点 x 的权重，用 C[x] 表示从根节点到节点 x 的所有节点的权重之和。
现在假设有一个查询，如 u, v:
我们必须找到节点 u 和 v 的最低公共(public)祖先。假设 u 和 v 的 LCA 是 P。所以查询 (u,v) 的结果将是 C[u]-C [P]+C[v]-C[P]+W[P]
关于algorithm - 树中两个节点之间路径的权重和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17962687/