首先如何刻画重边，每次操作相当于给路径染上不同的颜色，一条边是重边当且仅当满足两个端点颜色相同。初始全是轻边，只需要所有点颜色不一样。

使用树链剖分算法，问题被转化到一个类似区间染色，区间颜色段数的问题，可以用珂朵莉树解决，当然也可以用线段树，合并两个区间时只关注区间的端点颜色和内部颜色段数，可以 $O(1)$。

注意在树上合并若干段区间需要注意合并顺序问题。

时间复杂度为 $O(n\log^2 n)$。