带权树上选A,B,C三点，求A到B的距离+B到C的距离的最大值 O(nlogn)算法

可以使用LCA算法来求解。首先将树转换为带权树，然后预处理出每个节点向上跳2^k个祖先的距离和权值之和，然后在查询A到B的距离和B到C的距离的时候，找到他们的LCA，然后将LCA到A的路径、LCA到B的路径和LCA到C的路径的权值和分别求出来，再将这三个值相加，最后减去2倍的LCA到A、LCA到B、LCA到C的路径的权值和，就得到了AB、BC距离的最大值。这个算法的时间复杂度是O(nlogn)。

相关问题

带权树上选A,B,C三点,求A到B的距离+B到C的距离的最大值 O(nlogn)算法

可以使用倍增算法来解决这个问题，具体步骤如下：

1. 对于每个节点 v，计算出它到根节点的距离 dist[v]。

2. 预处理出每个节点的第 2^i 级祖先，记为 p[i][v]。

3. 对于任意两个节点 A、B，假设深度(A) > 深度(B)，令 A 向上跳到和 B 一样深度，然后同时向上跳，直到两个节点的祖先相同。

4. 在这个过程中，记录下每一步跳跃的最大值，即 max(dist[x][A], dist[x][B])，其中 x 是跳跃的节点。

5. 最后，返回所有最大值中的最大值即可。

该算法的时间复杂度为 O(nlogn)，其中 n 是树的节点数。

O(nlogn + n × Σ(C(n, i)) + len(combinations)log(len(combinations))) 和O（n*n）谁大

我们可以对比一下这两个复杂度的增长趋势。

首先，O(nlogn + n × Σ(C(n, i)) + len(combinations)log(len(combinations)))中 Σ(C(n, i)) 表示i从n到数组长度的组合数之和，因此 Σ(C(n, i)) 是一个非常大的数，即使 len(combinations) 比较小，这个复杂度也非常高。

而 O(n^2) 的复杂度是一个二次方的增长趋势，与数组长度的增长呈平方关系，当数组长度增长时，这个复杂度也会变得非常高。

因此，两个复杂度在数据规模较小的情况下可能相当，但在数据规模较大时，O(nlogn + n × Σ(C(n, i)) + len(combinations)log(len(combinations))) 的复杂度会更高。