1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import { UnionFind } from "../largest-component-size-by-common-factor/UnionFind.ts";function numberOfGoodPaths(vals: number[], edges: number[][]): number {    const n = vals.length;    const cnt = new Map<number, number[]>();
    for (const [i, v] of vals.entries()) {        const arr = cnt.get(v) ?? [];        arr.push(i);        cnt.set(v, arr);    }    edges.sort((a, b) =>        Math.max(vals[a[0]], vals[a[1]]) - Math.max(vals[b[0]], vals[b[1]])    );    const uf = new UnionFind();    let ans = n;    let j = 0;
    for (const [val, vec] of [...cnt.entries()].sort((a, b) => a[0] - b[0])) {        while (            j < edges.length && vals[edges[j][0]] <= val &&            vals[edges[j][1]] <= val        ) {            uf.union(edges[j][0], edges[j][1]);            j++;        }
        const count = new Map<number, number>();
        for (const v of vec) {            const key = uf.find(v);            count.set(key, (count.get(key) ?? 0) + 1);        }
        ans += [...count.values()].reduce(            (p, c) => p + Math.floor(c * (c - 1) / 2),            0,        );    }    return ans;}export default numberOfGoodPaths;