加权树中两个节点之间的距离
Distance between two nodes in a tree weighted
我的问题很直接。
A weighted tree is given. We must find the distance between two given nodes.
因为每次 bfs 超时时查询的数量都非常多（大约 75000）所以我尝试了不同的方法。
我的算法是这样的：
我 运行 从顶点 0 开始 dfs 并计算出从根 (0) 到所有顶点的距离，类似这样
depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)
一旦我使用 dfs 和每个节点的第 2^j 个父节点计算了所有节点的深度（假设我知道该怎么做）。我计算了 LCA for (u, v) 询问每个查询。
然后我这样计算距离
distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)]
但我没有像预期的那样得到正确的判决。我的算法是否正确，还是我遗漏了一些关键的东西。需要指导:)
P.s 如果有人想看我的实现-Link http://paste.ubuntu.com/13129038/
您的方法听起来很合理，但查看链接代码我建议您尝试一个小示例（例如树中有 3 个节点）并仔细检查父数组的内容。
据我所知，唯一改变父数组内容的行是：
memset(parent,-1,sizeof parent);
和
parent[i][j]=parent[i-1][parent[i-1][j]]
所以我相信 parent 的内容总是等于 -1。
也许您需要一个基本案例设置 parent[0][j] 等于 j 的父级？
此外，从代码中还不太清楚您是使用深度来表示边数的计数，还是所有边的权重之和。要使距离计算起作用，您需要权重总和，但要使 LCA 算法起作用，您可能会发现需要使用边数。
我的问题很直接。
A weighted tree is given. We must find the distance between two given nodes.
因为每次 bfs 超时时查询的数量都非常多（大约 75000）所以我尝试了不同的方法。
我的算法是这样的：
我 运行 从顶点 0 开始 dfs 并计算出从根 (0) 到所有顶点的距离，类似这样
depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)一旦我使用 dfs 和每个节点的第 2^j 个父节点计算了所有节点的深度（假设我知道该怎么做）。我计算了 LCA for (u, v) 询问每个查询。
然后我这样计算距离
distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)]
但我没有像预期的那样得到正确的判决。我的算法是否正确，还是我遗漏了一些关键的东西。需要指导:)
P.s 如果有人想看我的实现-Link http://paste.ubuntu.com/13129038/
您的方法听起来很合理，但查看链接代码我建议您尝试一个小示例（例如树中有 3 个节点）并仔细检查父数组的内容。
据我所知，唯一改变父数组内容的行是：
memset(parent,-1,sizeof parent);
和
parent[i][j]=parent[i-1][parent[i-1][j]]
所以我相信 parent 的内容总是等于 -1。
也许您需要一个基本案例设置 parent[0][j] 等于 j 的父级？
此外，从代码中还不太清楚您是使用深度来表示边数的计数，还是所有边的权重之和。要使距离计算起作用，您需要权重总和，但要使 LCA 算法起作用，您可能会发现需要使用边数。