Finc(x): find the root/cluster-id of x
Union(x, y): merge two clusters

Find: O(1)
Union: O(1)

without optimization: Find O(n)
Two key optimizations:
1) Path compression: make tree flat
2) Union by rank: merge low rank tree to high rank one

class UnionFindSet:
  func UnionFindSet(n):
    parents = [1..n] // 数组
    ranks = [0..0] (n zeros) // 数组

  func Find(x):
    if x != parents[x]:
      parents[x] = Find(parents[x])
    return parents[x]

  func Union(x, y):
    px, py = Find(x), Finx(y)
    if rank[px] > rank[py]: parents[py]=px
    if rank[px] < rank[py]: parents[px]=py
    if rank[px] == rank[py]:
       parents[py]=px
       rank[px]++


  class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始时每个节点的父节点是自己
        self.rank = [0] * n           # 初始时每个节点的秩都是0

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:  # 已经在同一集合中
            return

        if self.rank[px] > self.rank[py]:
            self.parent[py] = px
        elif self.rank[px] < self.rank[py]:
            self.parent[px] = py
        else:
            self.parent[py] = px
            self.rank[px] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

# 创建包含5个节点的并查集
uf = UnionFind(5)

# 合并节点
uf.union(0, 1)  # 合并0和1
uf.union(2, 3)  # 合并2和3
uf.union(1, 2)  # 合并1和2（同时会连接0,1,2,3）

# 检查连通性
print(uf.connected(0, 3))  # True
print(uf.connected(0, 4))  # False

type UnionFindSet struct {
	parents []int
	ranks   []int
}

func NewUnionFindSet(n int) *UnionFindSet {
	ufs := &UnionFindSet{
		parents: make([]int, n+1),
		ranks:   make([]int, n+1),
	}

	for i := 0; i < len(ufs.parents); i++ {
		ufs.parents[i] = i
	}
	return ufs
}

func (ufs *UnionFindSet) Union(u, v int) bool {
	pu := ufs.Find(u)
	pv := ufs.Find(v)

	if pu == pv {
		return false
	}

	if ufs.ranks[pv] < ufs.ranks[pu] {
		ufs.parents[pv] = pu
	} else if ufs.ranks[pu] < ufs.ranks[pv] {
		ufs.parents[pu] = pv
	} else {
		ufs.parents[pv] = pu
		ufs.ranks[pu] += 1
	}

	return true
}

func (ufs *UnionFindSet) Find(u int) int {
	if u != ufs.parents[u] {
		ufs.parents[u] = ufs.Find(ufs.parents[u])
	}
	return ufs.parents[u]
}

737 Sentence Similarity II
684 Redundant Connection
547 Friend Circles

Union-Find Problems:
* LeetCode 399. Evaluate Division https://youtu.be/UwpvInpgFmo
* LeetCode 547. Friend Circles https://youtu.be/HHiHno66j40
* LeetCode 737. Sentence Similarity II https://www.youtube.com/watch?v=0rZUi3kZGLI
* LeetCode 684. Redundant Connection https://www.youtube.com/watch?v=4hJ721ce010
* LeetCode 685. Redundant Connection II https://youtu.be/lnmJT5b4NlM
* LeetCode 839. Similar String Groups  https://zxi.mytechroad.com/blog/string/leetcode-839-similar-string-groups/
* LeetCode 959. Regions Cut By Slashes
LeetCode 399. Evaluate Division https://youtu.be/UwpvInpgFmo
LeetCode 547. Friend Circles https://youtu.be/HHiHno66j40
LeetCode 737.  Sentence Similarity II https://www.youtube.com/watch?v=0rZUi3kZGLI&t=0s
LeetCode 684. Redundant Connection https://www.youtube.com/watch?v=4hJ721ce010&t=0s
LeetCode 685. Redundant Connection  II https://youtu.be/lnmJT5b4NlM

class FenwickTree {
public:
		FenwickTree(int n): sums_(n + 1, 0) {}

		void update(int i, int delta){
				while (i < sums_.size()){
						sums_[i] += delta;
						i += lowbit(i);
				}
		}

		int query(int i) const {
				int sum = 0;
				while (i > 0){
						sum += sums_[i]
						i -= lowbit(i);
				}
				return sum;
		}
private:
		static inline int lowbit(int x) { return x & (-x); }
		vector<int> sums_;
}

quick_sort(a, l, r):
	p = partition(a, l, r) # O(r-l)
	quick_sort(a, l, p)
	quick_sort(a, p+1, r)

Bast case:
T(n) = 2*T(n/2) + O(n) = O(nlogn)
Worst case:
T(n) = T(n-1) + T(1) +O(n) = O(n2)
Non-worst cases:
T(n) = T(n/10） + T(9n/10) + O(n) = O(nlogn)

Space Best/Average: O(logn)
			Worst: O(n)

merge_sort(a, l, r):
	m = l + (r - l)/2
	merge_sort(a, l, m)
	merge_sort(a, m+1, r)
	merge_sort(a, l, m, r) # O(r - l)

Time:
T(n) = 2*T(n/2) + O(n) = O(nlogn)

Space:
O(logn + n)

binary_search(a, l, r):
	m = l + (r - l) / 2
	if f(m):
		binary_search(a, l, m)
	else:
		binary_search(a, m+1, r)

Time complexity:
T(n) = T(n/2) + O(1) = O(nlogn)

Space complexity:
O(logn)

inorder(root):
	inorder(root.left)
	func(rool.val)
	inorder(root.right)
Time complexity:
T(n) = 2*T(n/2) + O(1) = O(n) perfect
T(n) = T(n-1) + T(1) + O(1) = O(n) worst case

Space complexity:
O(logn) perfect
O(n) worst case

combination(d, s):
	if d == n:
		return func()
	for i in range(s, n):
		combination(d+1, i+1)
Time complexity:
T(n) = T(n-1) + T(n-2) + ... + T(1)
		 = O(2^n)

Space complexity:
O(n)

permutation(d, used):
	if d == n:
		return func()
	for i in range(0, n):
		if i in used: continue
		used.add(i)
		permutation(d+1, used)
		used.remove(i)
Time complexity:
T(n) = n * T(n-1)
		 = O(n!)
Space complexity:
O(n)

fib(n):
	if n < 1: return 0
	return fib(n-1) + fib(n-2)

T(n) = T(n-1) + T(n-2) + O(1)
	   = O(2^n)
	   = O(1.618^n)

fib(n):
	if n < 1: return 0
	if m[n] > 0: return m[n]
	m[n] = fib(n-1) + fib(n-2)
	return m[n]

n subproblems
each problem takes O(1) to solve
fib(n) takes O(n) time to solve

LC 741. Cherry pickup
dp(x1, y1, x2):
	if m[x1][y1][x2] != None:
		return m[x1][y1][x2]
	ans = max(max(dp(...), dp(...)),
						max(dp(...), dp(...)))
	m[x1][y1][x2] = ans
	return m[x1][y1][x2]

	n^3 subproblems
	Each subproblem takes O(1)

dp(n, n, n) takes O(n^3) to solve

LC 312. Burst Balloons

dp(i, j):
	if m[i][j] != None:
		return m[i][j]
	for k in range(i, j+1):
		ans = max(ans, dp(...) + C + dp(...))
	m[i][j] = ans
	return m[i][j]

	n^2 subproblems
	Each subproblem takes O(n)

	dp(n, n) takes O(n^2) to solve

Template:
[l, r)

def binary_search(l, r):
	while l < r:
		m = l + (r-l)/2
		if f(m): return m # optional
		if g(m):
			r = m # new range [l, m)
		else:
			l = m+1 # new range [m+1, r)
	return l # or not found

Time complexity: O(log(r-l)*(f(m)+g(m)))
Space complexity: O(1)

A = [1, 2, 5, 7, 8, 12]
search(8) = 4, search(6) = -1

def binary_search(A, val, l, r):
	while l < r:
		m = l + (r - l) // 2
		if A[m] == val: return m
		if A[m] > val:
			r = m
		else:
			l = m + 1
	return -1 # not found
binary_search(A, 8, 0, len(A))

def lower_bound(A, val, l, r):
	while l < r:
		m = l + (r - l)/2
		if A[m] >= val: # g(m)
			r = m
		else:
			l = m + 1
	return l

def upper_bound(A, val, l, r):
	while l < r:
		m = l + (r - l) // 2
		if A[m] > val: # g(m)
			r = m
		else:
			l = m + 1
	return l

def sqrt(x):
	l = 0
	r = x + 1
	while l < r:
		m = l + (r-l) // 2
		if m * m > x:
			r = m
		else:
			l = m + 1
	return l - 1 # l*l > x

def firstBadVersion(n):
	l = 0
	r = n
	while l < r:
		m = l + (r - l) // 2
		if isBadVersion(m):
			r = m
		else
			l = m + 1
	return l

def eat(piles, H):
	l = 1
	r = max(piles) + 1
	while l<r:
		m = l+(r-l)//2
		h = 0
		for p in piles: # O(n)
			h += (p + m - 1) / m
		if h <= H # g(m): can finish
			r = m
		else:
			l = m + 1
	return l

def KthSmallest(A, k):
	l = A[0][0]
	r = A[-1][-1]
	while l<r:
		m = l + (r - l) // 2
		total = 0
		for row in A:
			total += upper_bound(row, m)
		if total >= K:
			r = m
		else:
			l = m + 1
	return l

push(x):
	data[++size] = x
	if size == capacity:
		capacity *= 2
		new_data = data int[capacity]
		copy(new_data, data, size)
		data = new_data
Worst case push(x) takes O(n) time

# O(2^n) O(n)
def f(n):
	if n<=1: return 1
	return f(n-1) + f(n-2)

# O(n), O(n)
def f(n):
	if n<=1: return 1
	if n not in mem:
		mem[n] = f(n-1) + f(n-2)
	return mem[n]

f(4) -> f(3) -> f(2) -> f(1)
                     -> f(0)
						 -> f(1)

				f(2) -> f(1)
					   -> f(0)
Recursion has redundant computations

O(n), O(n)
def f(n):
	dp = [1] * (n + 1)
	for i in range(2, n+1):
		dp[i] = dp[i-1] + dp[i+2]
	return dp[n]

	# O(n), O(1)
	# One param, no loop
	def f(n):
		dp1, dp2 = 1, 1
		for i in range(2, n+1):
			dp2, dp1 = dp1+dp2, dp2
		return dp2

#O(mn), O(mn)
def f(x, y):
	if x<=0 or y<=0: return 0
	if x==1 or y==1: return 1
	return f(x-1, y) + f(x, y-1)

#O(mn), O(mn)
def f(x, y):
	if x<=0 or y<=0: return 0
	if x==1 and y==1: return 1
	if (x,y) not in mem:
		mem[(x,y)] = f(x-1,y) + f(x,y-1)
	return mem[(x,y)]

def f(x,y):
	dp = [[0] * (m+1) for _ in range(n+1)]
	dp[1][1] = 1
	for i in range(1, y+1):
		for j in range(1, x+1):
			dp[i][j] = dp[i-1][j] + dp[j][i-1]
	return dp[y][x]

# LC 926 Flip String to Monotone Increasing

for (int i = 1;i < n; ++i):
	l[i] = l[i-1] + S[i] - '0';
for (int i = n -2; i>=0; --i)
	r[i] = r[i+1] + '1' - S['i'];
int ans = r[0];
for (int i = 1; i<=n;++i)
	ans = min(ans, l[i-1] + r[i]);

LC 845. Longest Mountain in Array

for (int i = 1; i < A.size(); ++i)
	if (A[i] > A[i-1]) inc[i] = inc[i-1] + 1;
for (int i = A.size() -2; i>0; --i)
	if (A[i] > A[i+1) dec[i] = dec[i+1] + 1;
for ( int i =0; i< A.size(); ++i)
	if (inc[i] && dec[i])
		ans = max(ans, inc[i] + dec[i] + 1);

# LC 801. Minimun Swaps To Make Sequences Increasing
for i in range(1, n):
	if A[i] > A[i-1] and B[i] > B[i-1]:
		dp[i][0] = dp[i-1][0]
		dp[i][1] = dp[i-1][1] + 1
	if B[i] > A[i-1] and A[i] > B[i-1]:
		dp[i][0] = min(dp[i][0], dp[i-1][1])
		dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)

LC 926. Flip String to Monotone Increasing

for i in range(1, n+1):
	if S[i-1] == '0':
		dp[i][0] = dp[i-1][0]
		dp[i][1] = min(dp[i-1][0], dp[i-1][1] + 1
	else:
		dp[i][0] = dp[i-1][0] + 1
		dp[i][1] = min(dp[i-1][0] + dp[i-1][1])

LC 790. Domino and Tromino Tilling

for i in range(2, n+1):
	dp[i][0] = (dp[i-1][0] + dp[i-2][0]
							+ 2 * dp[i-1][1] % kMod)
  dp[i][1] = (dp[i-2][0] + dp[i-1][1]) % kMod

LC 818. Race car
for i in range(1, t+1):
	c = min(dp[i][0] + 2, dp[i][1] + 1)
	dp[t][0] = min(dp[t][0], dp[t-1][0] + c)
	dp[t][1] = min(dp[t][1], dp[t-1][0] + c)

dp = … # create dp array
			 # add padding if needed
dp[0][0] = … # init dp array
             # base cases
for i ...
	for j ...
		...
		dp[i][j] = ... # transition
return dp[n][m]

mem = ... # create mem dict

def dp(i, j, ...):
	if base_case(i, j): return ... # base cases
	if (i, j) not in mem:
		mem[(i, j)] = ...            # transition
	return mem[(i, j)]

return dp(n, m)

Input: O(n)
Sub-problems: O(n)
Each sub-problem depends on O(1) smaller problems
Time complexity: O(n)
Space complexity: O(n) -> O(1)
dp[i] := solution of A[1->i] // prefix

dp = new int[n + 1]
for i = 1 to n:
  dp[i] = f(A[i], dp[i-1], dp[i-2], ...)
return dp[n]

dp = new int[n]
for i = 1 to n:
  for j = 1 to l-1:
    dp[i] = max/min(dp[i], f(dp[j]))
return d[n]

dp = new int[n]
for i = 1 to n:
  for j = 1 to l-1:
    dp[i] = max/min(dp[i], f(dp[j]))
return d[n]

dp = new int[n]
for i = 1 to n:
  for j = 1 to l-1:
    dp[i] = max/min(dp[i], f(dp[j]))
return d[n]

dp = new int[n]
for i = 1 to n:
  for j = 1 to l-1:
    dp[i] = max/min(dp[i], f(dp[j]))
return d[n]

dp = new int[K][n][m]
for k = 1 to K:
  for i = 1 to n:
    for j = 1 to m:
      dp[k][i][j] = f(dp[k-1][i+di][j+dj])
return dp[K][n][m] / g(dp[K])

def dfs(s, cur_w, cur_v):
	ans = max(ans, cur_v)
	if s > N: return
	for i in range(s, N+1):
		if cur_w + w[i] <= W:
			dfs(i+1, cur_w + w[i], cur_v + v[i])

def knapscake01(w, v):
	ans = 0
	dfs(1, 0, 0)
	return ans

def knapsack01DFS(w, v, W):
  def dfs(s, cur_w, cur_v, ans):
    ans[0] = max(ans[0], cur_v)
    if s == N: return
    for i in range(s, N):
      if cur_w + w[i] <= W:
        dfs(i + 1, cur_w + w[i], cur_v + v[i], ans)
  ans = [0]
  dfs(0, 0, 0, ans)
  return ans[0]

def knapsack01(w, v, W):
  dp = [[0] * (W + 1) for _ in range(N+1)]
  for i in range(1, N + 1):
    # dp[i] = dp[i-1].clone()
    for j in range(1, W + 1):
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
  return max(dp[N])

# dp pull
def knapsack01R(w, v, W):
  dp = [0] * (W + 1)
  for i in range(0, N):
    tmp = list(dp)
    for j in range(w[i], W + 1):
      tmp[j] = max(tmp[j], dp[j - w[i]] + v[i])
    dp = tmp
  return max(dp)

# dp push
def knapsack01R(w, v, W):
  dp = [0] * (W + 1)
  for i in range(0, N):
    tmp = list(dp)
    for j in range(w[i], W + 1):
      tmp[j] = max(tmp[j], dp[j - w[i]] + v[i])
    dp = tmp
  return max(dp)

# dp pull
def knapsack01R1(w, v, W):
  dp = [0] * (W + 1)
  for i in range(0, N):
    for j in range(W - w[i], -1, -1):
      dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])
  return max(dp)

dp[i][j] := max value of using first i items and total weight is exact j.

dp[i][j] = max(dp[i-1][j],             # i-th item not used
               dp[i-1][j-w[i]]+v[i])   # i-th item used

for i = 1 to N:
	for j = 0 to W:
		dp[i][j] = max(dp[i-1][j],
								   dp[i-1][j-w[i] + v[i])
return max(dp[N])

def knapsack01(w, v):
	for j = W to w:
		dp[j] = max(dp[j], dp[j-w] + v)
for i = 1 to N:
	knapsack01(w[i], v[i])
return max(dp[N]

def main():
	for i = 1 to N:
		for j = 1 to W/w[i]:
			knapsack01(w[i], v[i])

def main():
	for i = 1 to N:
		for k = 1 to log(W/w[i]):
			knapsack01(w[i] << k, v[i] << k)

def knapsackUnbounded(w, w):
	for j = w to W:
		dp[j] = max(dp[j], dp[j-w] + v)
for i = 1 to N:
	knapsackUnbounded(w[i], v[i])
return max(dp)

public class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {val = x;}
}

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

struct TreeNode{
	int val;
	TreeNode* left = nullptr;
	TreeNode* right = nullptr;
	TreeNode(int x): val(x) {}
	~TreeNode(){
		delete left;
		delete right;
		left = nullptr;
		right = nullptr;
	}
};

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
delete root;

To create a tree

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.right = TreeNode(5)
root.right.left = TreeNode(6)
    1
   / \
  2   3
 /   /
4    6
 \
  5

GOOD
        5
       /
      4
     /
    3
   /
  2
 /
1

  GOOD
        5
       / \
      3   7
     /   /
    1   6

BAD
        5
       / \
      3   7
     /   /
    1   4

func search(root, x):
	if not root: return False
	if x == root.val: return True
	if x < root.val:
		return search(root.left, x)
	else:
		return search(root.right, x)

Time complexity: O(h)

Worst case: O(h) = O(n)
Best case: O(h) = O(logn)

def balanced(root):
	if not root: return True
	return abs(height(root.left) - height(root.right)) <= 1
	and balanced(root.left) and balanced(root.right)

def height(root):
	if not root: return 0
	left = height(root.left)
	right = height(root.right)
	return max(left, right) + 1

        5
       /
      4
     /
    3
   /
  2
 /
1
A BST but not balanced inefficient

       5
     /   \
    4     7
   / \   /
  2   3 4
 /
1
A balanced tree but not a BST
Not useful at all

     5
   /   \
  3    7
 / \  /
1   4 6
A perfect BST
O(h) = O(logn)

def perorder(root):
	if not root: return
	print(root.val)
	perorder(root.left)
	perorder(root.right)
# [5, 3, 1, 4, 7, 6]

def inorder(root):
	if not root: return
	inorder(root.left)
	print(root.val)
	inorder(root.right)
# [1, 3, 4, 5, 6, 7]
# For a BST the vals are sorted!

def postorder(root):
	if not root: return
	postorder(root.left)
	postorder(root.right)
	print(root.val)
# [1, 4, 3, 6, 7, 5]

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def createBST(nums):
    root = None
    for num in nums:
        root = insert(root, num)
    return root

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val <= root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def inorder(root, v):
    if not root:
        return
    inorder(root.left, v)
    v.append(root.val)
    inorder(root.right, v)

if __name__ == '__main__':
    root = createBST([5, 3, 1, 4, 7, 6])
    v = []
    inorder(root, v)
    print(v)

// insert returns the new root of the sub

# Traditional way:
ans = -inf
def maxVal(root):
	ans = -inf
	traverse(root)
	return ans

def traverse(root):
	if not root: return
	ans = max(ans, root.val)
	traverse(root.left)
	traverse(root.right)

# Recursive way:
def maxVal(root):
	if not root: return -inf
	max_left = maxVal(root.left)
	max_right = maxVal(root.right)
	return max(max_left, max_right)

def solve(root):
	if not root: return ...
	if f(root): return ...
	l = solve(root.left)
	r = solve(root.rigth)
	return g(root, l, r)

# LC 104. Maximum Depth of Binary Tree.
def maxDepth(root):
	if not root: return 0
	l = maxDepth(root.left)
	r = maxDepth(root.right)
	return max(l, r) + 1

# LC 111. Minium Depth of Binary Tree
def minDepth(root):
	if not root: return 0
	if not root.left and not root.right: return 1
	l = minDepth(root.left)
	r = minDepth(root.right)
	if not root.left: return 1 + r
	if not root.right: return 1 + l
	return min(l, r) + 1

# LC 112. Path Sum.
def pathSum(root, sum):
	if not root: return false
	if not roo.left and not root.right: return root.val == sum
	l = pathSum(root.left, sum - root.val)
	r = pathSum(root.right, sum - root.right)
	return l or r

def solve(p, q):
	if not p and not q: return ...
	if f(p, q): return ...
	c1 = solve(p.child, q.child)
	c2 = solve(p.child, q.child)
	return g(p, q, c1, c2)

# LC 100. Same Tree
def sameTree(p, q):
	if not p and not q: return True
	if not p or not q: return False
	l = sameTree(p.left, q.left)
	r = sameTree(p.right, q.right)
	return p.val == q.val and l and r

# LC 101. Symmetric Tree
def sameTree(p, q):
	if not p and not q: return True
	if not p or not q: return False
	l = sameTree(p.left, q.right)
	r = sameTree(p.right, q.left)
	return p.val == q.val and l and r

# LC 951. Flip Equivalent Binary Trees
def flipEquiv(p, q):
	if not p and not q: return True
	if not p or not q: return False
	l1 = flipEquiv(p.left, q.left)
	l2 = flipEquiv(p.left, q.right)
	r1 = flipEquiv(p.right, q.right)
	r2 = flipEquiv(p.left, q.right)
	return p.val == q.val and ((l1 and r1) or (l2 and r2))

nums = […]
ans = []
m = len(nums)
# C(m, n)
def dfs(n, s, cur):
	if len(cur) == n:
		ans.append(cur[:])
		return
	for i in range(s, m):
		cur.append(nums[i])
		dfs(n, i+1, cur)
		cur.pop()

	for i in range(0, m+1):
		dfs(i, 0, [])

n=0
ans.append(cur)

n=1
for i in range(0, m):
	cur.append(nums[i]
	ans.append(cur)
	cur.pop()

n=2
for i in range(0, m):
	cur.append(nums[i])
	for j in range(i, m):
		cur.append(nums[j])
		ans.append(cur)
		cur.pop()
	cur.pop()

n=3
for i in range(0, m):
	cur.append(nums[i])
	for j in range(i+1, m):
		cur.append(nums[j])
		for k in range(j+1, m):
			cur.append(nums[k])
			ans.append(cur)
			cur.pop()
		cur.pop()
	cur.pop()

n=4
for i in range(0, m):
	cur.append(nums[i])
	for j in range(i+1, m):
		cur.append(nums[j])
		for k in range(j+1, m):
			cur.append(nums[k])
			for l in range(k+1, m):
				cur.append(nums[l])
				ans.append(cur)
				cur.pop()
			cur.pop()
		cur.pop()
	cur.pop()

nums = [...]
ans = []
m = len(nums)

# C(m, n)
def dfs(n, d, s, cur):
	if d == n:
		ans.append(cur[0:d])
		return
	for i in range(s, m):
		cur[d] = nums[i]
		dfs(n, d+1, i+1, cur)
		~~cur[d] = None~~

for i in range(0, m+1):
	dfs(i, 0 [None]*i)

n = 0
ans.append(cur)

n = 1
for i range(0, m):
	cur[0] = nums[i]
	ans.append(cur)

n = 2
for i range(0, m):
	cur[0] = nums[i]
	for j in range(i+1, m):
		cur[1] = nums[j]
		ans.append(cur)

n = 3
for i range(0, m):
	cur[0] = nums[i]
	for j in range(i+1, m):
		cur[1] = nums[j]
		for k in range(j+1, m):
			cur[2] = nums[k]
			ans.append(cur)

n = 4
for i range(0, m):
	cur[0] = nums[i]
	for j in range(i+1, m):
		cur[1] = nums[j]
		for k in range(j+1, m):
			cur[2] = nums[k]
			for l in range(k+1, m):
				cur[3] = nums[l]
				ans.append(cur)

nums = [...]
ans = []
m = len(nums)
used = [False] * m

# P(m, n)
def dfs(n, cur):
	if len(cur) == n:
		ans.append(cur[:])
		return
	for i range(0, m):
		if used[i]: continue
		used[i] = True
		cur.append(nums[i])
		dfs(n, cur)
		cur.pop()
		used[i] = False

for i in range(0, len(nums)+1):
	dfs(i, [])

n = 0
ans.append(cur)

n = 1
for i in range(0, m):
	if used[i]: continue
	used[i] = True
	cur.append(nums[i])
	ans.append(cur)
	cur.pop()
	used[i] = False

n = 2
for i in range(0, m):
	if used[i]: continue
	cur.append(nums[i])
	for j in range(0, m):
		if used[j]: continue
		used[j] = True
		cur.append(nums[j])
		ans.append(cur)
		cur.pop()
		used[j] = False
	cur.pop()
	used[i] = False

n = 3
for i in range(0, m):
	if used[i]: continue
	used[i] = True
	cur.append(nums[i])
	for j in range(0, m):
	  if used[j]: continue
		used[j] = True
		cur.append(nums[j])
		for k in range(0, m):
			if used[k]: continue
			used[k] = True
			cur.append(nums[k])
			ans.append(cur)
			cur.pop()
			usded[k] = False
		cur.pop()
		used[j] = False
	cur.pop()
	used[i] = False

	       15
	      [0-4]
	     /.   \
	    8      7
	  [0-2]  [3-4]
	   / \    / \
	  3   5  3   4
	[0-1][2][3] [4]
	 / \
	2   1
 [0] [1]

nums = [2, 1, 5, 3, 4]

class SegmentTreeNode:
    def __init__(self, start, end, sum, left=None, right=None):
        self.start = start
        self.end = end
        self.sum = sum
        self.left = left
        self.right = right

def buildTree(start, end, vals):
    if start == end:
        return SegmentTreeNode(start, end, vals[start])
    mid = (start + end) // 2  # 使用整除
    left = buildTree(start, mid, vals)
    right = buildTree(mid+1, end, vals)
    return SegmentTreeNode(start, end, left.sum + right.sum, left, right)

def updateTree(root, index, val):
	if root.start == root.end == index:
		root.sum = val
		return
	mid = (root.start + root.end) // 2
	if index <= mid:
		updateTree(root.left, index, val)
	else:
		updateTree(root.right, index, val)
	root.sum = root.left.sum + root.right.sum

# updateTree: Similar to binary search
# T(n) = T(n/2) + O(1) = log(n)
# Don't forget to update root's sum

def querySum(root, i, j):
    if root.start == i and root.end == j:
        return root.sum
    mid = (root.start + root.end) // 2
    if j <= mid:
        return querySum(root.left, i, j)
    elif i > mid:
        return querySum(root.right, i, j)
    else:
        return querySum(root.left, i, mid) + querySum(root.right, mid+1, j)
# QueryTree: O(log(n) + k)
# Ex 1: querySum(n15, 3, 4)[7]
#				querySum(n7, 3, 4) <- 7

# Ex 2: querySum(n15, 2, 2)[5]
# 				querySum(n8, 2, 2][5]
# 					querySum(n5, 2, 2] <- 5

# Ex 3: querySum(n15, 1, 3)[9]
#				querySum(n8, 1, 2)[6]                             + querySum(n7, 3, 3)[3]
# 					querySum(n3, 1, 1[1] + querySum(n5, 2, 2) <- 5      querySum(n3, 3, 3) <- 3
#						querySum(n1, 1, 1) <- 1

# 测试用例
nums = [2, 1, 5, 3, 4]
root = buildTree(0, len(nums) - 1, nums)

# 验证线段树
def printTree(node):
    if node is not None:
        print(f"[{node.start}, {node.end}] : {node.sum}")
        printTree(node.left)
        printTree(node.right)

print("更新前的线段树")
printTree(root)

updateTree(root, 2, 10) # 将索引 2 的值更新为 10

print("更新后的线段树")
printTree(root)

print("查询区间 [1,3] 的和：", querySum(root, 1, 3))
print("查询区间 [0,4] 的和：", querySum(root, 0, 4))
print("查询区间 [2,2] 的和：", querySum(root, 2, 2))

class SegmentTreeNode {
public:
  SegmentTreeNode(int start, int end, int sum,
                  SegmentTreeNode* left = nullptr,
                  SegmentTreeNode* right = nullptr):
    start(start),
    end(end),
    sum(sum),
    left(left),
    right(right){}
  SegmentTreeNode(const SegmentTreeNode&) = delete;
  SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;
  ~SegmentTreeNode() {
    delete left;
    delete right;
    left = right = nullptr;
  }

  int start;
  int end;
  int sum;
  SegmentTreeNode* left;
  SegmentTreeNode* right;
};

class NumArray {
public:
  NumArray(vector<int> nums) {
    nums_.swap(nums);
    if (!nums_.empty())
      root_.reset(buildTree(0, nums_.size() - 1));
  }

  void update(int i, int val) {
    updateTree(root_.get(), i, val);
  }

  int sumRange(int i, int j) {
    return sumRange(root_.get(), i, j);
  }
private:
  vector<int> nums_;
  std::unique_ptr<SegmentTreeNode> root_;

  SegmentTreeNode* buildTree(int start, int end) {
    if (start == end) {
      return new SegmentTreeNode(start, end, nums_[start]);
    }
    int mid = start + (end - start) / 2;
    auto left = buildTree(start, mid);
    auto right = buildTree(mid + 1, end);
    auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);
    return node;
  }

  void updateTree(SegmentTreeNode* root, int i, int val) {
    if (root->start == i && root->end == i) {
      root->sum = val;
      return;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (i <= mid) {
      updateTree(root->left, i, val);
    } else {
      updateTree(root->right, i, val);
    }
    root->sum = root->left->sum + root->right->sum;
  }

  int sumRange(SegmentTreeNode* root, int i, int j) {
    if (i == root->start && j == root->end) {
      return root->sum;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (j <= mid) {
      return sumRange(root->left, i, j);
    } else if (i > mid) {
      return sumRange(root->right, i, j);
    } else {
      return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
    }
  }
};

"""
Returns the smallest number m in range [l, r) such
that g(m) is true. Returns r if not found.
"""
def binary_search(l, r):
    while l < r:
        m = l + (r - l) // 2
        if g(m):
            r = m
        else:
            l = m + 1
    return l

"""
Returns the smallest number m in range [l, r] such that g(m) is true.
Returns r if not found.
"""
def binary_search(l, r):
    while l <= r:
        m = l + (r - l) // 2
        if g(m):
            r = m - 1
        else:
            l = m + 1
    return l

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
  const int n = 4;
  vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};
  vector<vector<pair<int, int>>> g(n);
  for (const auto& e : edges) {
    g[e[0]].emplace_back(e[1], e[2]);
    g[e[1]].emplace_back(e[0], e[2]);
  }

  priority_queue<pair<int, int>> q; // (-w, v)
  vector<int> seen(n);
  q.emplace(0, 0); // (-w, v)

  int cost = 0;
  for (int i = 0; i < n; ++i) {
    while (true) {
      const int w = -q.top().first;
      const int v = q.top().second;
      q.pop();
      if (seen[v]++) continue;
      cost += w;
      for (const auto& p : g[v]) {
        if (seen[p.first]) continue;
        q.emplace(-p.second, p.first);
      }
      break;
    }
  }
  cout << cost << endl;
  return 0;
}

from collections import defaultdict
from heapq import *

n = 4
edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]
g = defaultdict(list)
for e in edges:
  g[e[0]].append((e[1], e[2]))
  g[e[1]].append((e[0], e[2]))

q = []
cost = 0
seen = set()
heappush(q, (0, 0))
for _ in range(n):
  while True:
    w, u = heappop(q)
    if u in seen: continue
    cost += w
    seen.add(u)
    for v, w in g[u]:
      if v in seen: continue
      heappush(q, (w, v))
    break

print(cost)

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <numeric>
using namespace std;

int main(int argc, char** argv) {
  const int n = 4;
  vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};
  vector<vector<int>> q; // (w, u, v)
  for (const auto& e : edges)
    q.push_back({e[2], e[0], e[1]});
  sort(begin(q), end(q));

  vector<int> p(n);
  iota(begin(p), end(p), 0);

  function<int(int)> find = [&](int x) {
    return x == p[x] ? x : p[x] = find(p[p[x]]);
  };

  int cost = 0;
  for (const auto& t : q) {
    int w = t[0], u = t[1], v = t[2];
    int ru = find(u), rv = find(v);
    if (ru == rv) continue;
    p[ru] = rv; // merge (u, v)
    cost += w;
  }
  cout << cost << endl;

  return 0;
}

from collections import defaultdict
from heapq import *
n = 4
edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]
p = list(range(n)

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

cost = 0
for u, v, w in sorted(edges, key=lambds x: x[2]):
	ru, rv = find(u), find(v)
	if ru == rv: continue
	p[ru] = rv
	cost += w

print(cost)

def match(s, p):
    """
    Args:
    s: input string
    p: pattern to search
    """
    ans = []        # matched indices
    nxt = build(p)  # build next table
    n = len(s)
    m = len(p) # added len of pattern to avoid calling len many times
    j = 0
    for i in range(n):  # i, j: pointer of s and p respectively
        while j > 0 and s[i] != p[j]:
            j = nxt[j]  # Accessing the correct nxt index

        if s[i] == p[j]: # match then check next pair (i++, j++)
            j += 1

        if j == m:   # found a full match
            ans.append(i - m + 1)
            j = nxt[j]    # jump as it failed
    return ans

def build(p):
    """
    build the next array for KMP algorithm
    """
    m = len(p)
    nxt = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = nxt[j-1]
        if p[i] == p[j]:
            j += 1
        nxt[i] = j
    return nxt
  # nxt[i] 表示 p 的前 i+1 个字符（p[0...i]）中，最长公共前缀后缀的长度