维护两个并查集

对于本题，只需要维护uf1和uf2两个并查集，其中uf1连接所有权值<=R的边，uf2连接所有权值<L的边，如果两个城市在uf1中连通但在uf2中不连通，说明这就是我们需要的一对城市

以下为go代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "runtime/debug"
)

func init() { debug.SetGCPercent(-1) } // 关闭gc，加速

func Run(_r io.Reader, _w io.Writer) {
    // 快读
    in := bufio.NewReader(_r)
    out := bufio.NewWriter(_w)
    defer out.Flush()

    var n, m, l, r int
    fmt.Fscan(in, &n, &m, &l, &r)

    uf1 := NewUnionFind(n + 1)
    uf2 := NewUnionFind(n + 1)

    for i := 0; i < m; i++ {
        var u, v, w int
        fmt.Fscan(in, &u, &v, &w)
        if w <= r {
            uf1.union(u, v)
            if w < l {
                uf2.union(u, v)
            }
        }
    }

    var ans int64
    for i := 1; i <= n; i++ {
        if i == uf1.find(i) {
            ans += cal(uf1.size[i])
        }
        if i == uf2.find(i) {
            ans -= cal(uf2.size[i])
        }
    }

    fmt.Fprintln(out, ans)
}

// 并查集模板部分，cal函数用于计算一个连通块中有多少城市组合
type UnionFind struct {
    fa   []int
    size []int
}

func NewUnionFind(n int) *UnionFind {
    fa := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        fa[i] = i
        size[i] = 1
    }
    return &UnionFind{fa, size}
}

func (uf *UnionFind) find(x int) int {
    if uf.fa[x] != x {
        uf.fa[x] = uf.find(uf.fa[x])
    }
    return uf.fa[x]
}

func (uf *UnionFind) union(x, y int) {
    rx, ry := uf.find(x), uf.find(y)
    if rx == ry {
        return
    }
    uf.fa[ry] = rx
    uf.size[rx] += uf.size[ry]
}

func cal(x int) int64 {
    return int64(x) * int64(x-1) / 2
}

func main() {
    Run(os.Stdin, os.Stdout)
}