## Q1 : Union Find Python3

https://leetcode.com/discuss/interview-question/2260088/Special-Paths-or-Google-OA-or-July-2022-or-Graph

Credit : @leetcode_dafu

```
def countSpecialPaths(n:int, edges:List[List[int]], value:int)->int:
# n and value are 0 indexed but given nodes are 1 indexed
n, value = n+1, [0]+value # make n and value 1 indexed
# Make graph
adjList = defaultdict(list) # record the neighbors for every node
for u,v in edges:
adjList[u].append(v)
adjList[v].append(u)
# union find
parent = list(range(n))
# find the Absolute parent
def findAP(curr):
if parent[curr] == curr:
return curr
parent[curr] = findAP(parent[curr])
return parent[curr]
subtree = [[val,1] for val in value] # [maxVal,maxValCount]
res = 0
for curr in sorted(range(n),key=lambda i: value[i]): # add nodes from low to high to adj sub-trees
currAP = findAP(curr)
for adj in adjList[curr]:
adjAP = findAP(adj)
if currAP==adjAP or value[adj] > value[curr] : # ignore adj with val>value[curr] because they will be added later.
continue
# if curr Sub tree max value is equal to adj Sub tree max value we find one of its path
# check how many nodes in the subtree have the same val of the curr
if subtree[currAP][0] == subtree[adjAP][0] :
res += subtree[currAP][1]*subtree[adjAP][1] # total combinations is the no of paths
subtree[currAP][1] += subtree[adjAP][1] # get count of max val in both subtree
subtree[adjAP] = subtree[currAP][:] # both curr ap and adj ap subtree are same i.e maxVal and maxValCount are same
parent[adjAP] = currAP # union currAP to adjAP subtrees
return res
print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,3,1,2,3]))
print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,2,1,2,3]))
print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,2,1,2,2]))
print(countSpecialPaths(6, [ [1, 2], [1, 3], [3, 5], [3, 4], [2, 6] ], [ 2, 3, 1, 2, 3, 3 ]))
```