给你一棵有 n 个顶点的树。每个节点都有一个与之关联的整数权重。给定的树上有大量的查询（~n^2）。对于查询（A，B），其中A，B是树的两个顶点，您需要计算从A到B的唯一路径上的节点的权重之和，包括A和B。
我可以为单个查询执行 dfs/bfs ，但是对于 ~n^2 可能的查询，这将需要 O(n^3) .. 谁能提出更好的建议，每个查询需要少于 O(n) 的时间？
谢谢..
问问题
3371 次
2 回答
3
如果树没有根，则将任意节点设为树的根。
我们将用 W[x] 表示节点 x 的权重，用 C[x] 表示从根到节点 x 的所有节点的权重之和。
现在让我们假设有一个查询，如u, v：
我们必须找到节点 u 和 v 的最低共同祖先。假设 u 和 v 的 LCA 是 P。所以查询 (u,v) 的结果将是C[u]-C[P]+C[v]-C[P]+W[P]
于 2013-07-31T06:06:05.390 回答
1
你的问题是不是和Timus Online Judge 1471.Tree 很像？唯一的区别是节点在您的问题中加权，而边缘在 Ural 1471.Tree 中加权。
这是一个典型的 LCA 问题。
将任何一个节点作为树的根（如果需要），然后计算每个其他节点到根的距离 dist[i]，使用 BFS/DFS 需要 O(N) 时间。然后对于每个query(A,B)，求(A,B)的LCA L，那么(A,B)之间的距离就是dist[A] + dist[B] - 2*dist[L]。
但是，在您的问题中，可能需要将节点权重转换为边权重。
如果您不熟悉 LCA 算法，这里有一个非常好的网站，可能会对您有所帮助。
于 2013-07-31T07:35:56.747 回答