Today's Challenge

https://leetcode.com/problems/number-of-good-paths/

Number of Good Paths - LeetCode

길찾기 관련 문제가 계속 나오네 ㅠ_ㅠ
오늘도 무지성 솔루션 복붙 ㅠ_ㅠ

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        n = len(vals)
        p = list(range(n))
        count = [Counter({vals[i]:1}) for i in range(n)] 
        edges = sorted((max(vals[i], vals[j]), i, j) for i, j in edges)
        res = n

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        for val, i, j in edges:
            pi, pj = find(i), find(j)
            res += count[pi][val] * count[pj][val]
            p[pi] = pj
            count[pj][val] += count[pi][val]
        
        return res