给定一个包含 N 个节点和 M 条边的无向带权图，我们的任务是针对每一条边 (u, v)，找出包含该边 (u, v) 的生成树可能的最小权重。边以二维数组 edges[][] 的形式给出，其中 edges[i] = {u, v, w} 表示从节点 u 到节点 v 有一条权重为 w 的有向边（注：虽描述为有向，但在生成树问题中通常视为无向边处理，即连接 u 与 v）。
示例：
> 输入： N = 5, M = 7, edges = {{1, 2, 3}, {1, 3, 1}, {1, 4, 5}, {2, 3, 2}, {2, 5, 3}, {3, 4, 2}, {4, 5, 4}}
> 输出： 9 8 11 8 8 8 9
> 解释：
> !tree
>
> – 对于 边 (1, 2)，最小生成树将包含边：，权重 = 3 + 1 + 2 + 3 = 9
> – 对于 边 (1, 3)，最小生成树将包含边：，权重 = 1 + 2 + 2 + 3 = 8
> – 对于 边 (1, 4)，最小生成树将包含边：，权重 = 1 + 2 + 5 + 3 = 11
> – 对于 边 (2, 3)，最小生成树将包含边：，权重 = 1 + 2 + 2 + 3 = 8
> – 对于 边 (2, 5)，最小生成树将包含边：，权重 = 1 + 2 + 2 + 3 = 8
> – 对于 边 (3, 4)，最小生成树将包含边：，权重 = 1 + 2+ 2 + 3 = 8
> – 对于 边 (4, 5)，最小生成树将包含边：，权重 = 1 + 2 + 2 + 4 = 9
>
> 输入： N =2, M = 1, edges = {1, 2, 42}
> 输出： 42
解决思路： 我们可以通过以下方法来解决这个问题：
> 首先，我们构建最小生成树 (MST) 以确保整体连接权重最小。然后，对于所有位于 MST 中的边，答案直接就是 MST 的总权重。对于不在 MST 中的边，比如 (u, v)，我们将移除节点 u 到节点 v 路径上权重最大的边，并添加边 (u, v)。
>
> 为了找到节点 u 到节点 v 路径上权重最大的边，我们分别计算从节点 u 到节点 l 以及从节点 v 到节点 l 的最大权重边，其中 l 是节点 u 和节点 v 的最近公共祖先。我们利用倍增法预处理祖先和最大权重信息，以便进行高效查询。这允许我们通过快速找到最近公共祖先 (LCA) 并结合已覆盖的最大权重来调整 MST 权重，从而快速分析单条边，最终得出包含每条边的最小生成树权重。
解决问题的步骤：
- 使用 Kruskal 算法构建 MST。
- 预处理以实现高效查询：
- 从任意节点开始执行深度优先搜索 (DFS)。
- 对于每个访问过的节点，更新其所有后代在不同层级的祖先信息和 maxWeight[] 数组。
- 使用 倍增法 为每个子节点计算祖先和 maxWeight[]。
- 处理边查询：
- 对于每条边，使用 included 数组检查该边是否已包含在 MST 中。
- 如果该边包含在 MST 中，答案即为 MST 的权重。
- 否则，找到边端点的 LCA，通过加上当前边的权重并减去存储在 maxWeight[] 数组中到 LCA 路径上的最大权重，来计算调整后的 MST 权重。
- 打印调整后的 MST 权重。
下面是上述方法的实现：
C++
#include
#define int long long
#define pii pair
using namespace std;
const int N = 200005;
// Arrays to store ancestor, depth, and maxWeight
// information
int ancestor[N][50], depth[N], maxWeight[N][50];
// Arrays to store parent and subtreeSize for union-find
int parent[N], subtreeSize[N];
// Array to mark included edges in the minimum spanning tree
bool included[N];
// Adjacency list to represent the graph
vector adjacencyList[N];
// Function to find the Lowest Common Ancestor (LCA) and
// maximum weight on the path
int findLCA(int u, int v)
{
int ans = -1;
if (depth[u] != depth[v]) {
if (dept