# Orange Lecture #04 - Distance in tree

### 1, Đề bài
- Cho một cây vô hướng n đỉnh.
Đếm số cặp đỉnh có khoảng cách bằng k

#### Input:
- n k
- n - 1 dòng tiếp theo:
- a b mô tả một cạnh
#### Output:
- kết quả


### 2, Ý tưởng & thuật toán

a) Dfs từ mọi đỉnh

result = 0

# dfs function
def dfs(u, distanceFromRoot = 0):
    visited[u] = True
    if(distanceFromRoot == k): result += 1
        
    # from u, traverse to u's child nodes
    for v in graph[u]:
        if(visited[v]): continue
        dfs(v, distanceFromRoot + 1)
        
For u = 1 -> n:
    visited = [False] * n
    dfs(u) # u is the root
    
print(result//2)

=> O(N^2)

b) Dfs

- Ý tưởng: **dist(u, v) = dist(u, c) + dist(v, c) với c = lca(u,v)** là tổ tiên chung gần nhất của u và v


- **Với mỗi node c: có bao nhiêu cặp (u, v) có lca là c và khoảng cách = k?**
=> u, v phải thuộc 2 nhánh con khác nhau của c
+ Giả sử 2 nhánh con đó là v1 và v2, u thuộc v1 và v thuộc v2

=> dist(u, v) = dist(u, c) + dist(v, c) = dist(u, v1) + 1 + dist(v, v2) + 1 = k
<=> **dist(u, v1) = k - 2 - dist(v, v2)**
Đặt **leftDist** = dist(u, v1), **rightDist** = dist(v, v2)


for c:
    for v1 != v2: #v1, v2 are children of c
        for leftDist = 0 -> k - 2:
            rightDist = k - 2 - leftDist
            result += countDescendants(v1, leftDist) * countDescendants(v2, rightDist)
            # countDescendants(x, d) = number of descendants of x whose distance to x = d

- Làm sao để tính countDescendants(x, d)?
+ **countDescendants[x][d] = sum(countDescendants[y][d - 1])** với y là node con của x


result = 0

bool visited[N]
int distanceFromRoot[N]
int countDescendants[N][K]
list graph[N] # graph[u] = list of neighbors of u

# dfs function
def dfs(c, parent = 0):
    distanceFromRoot[c] = distanceFromRoot[parent] + 1
    visited[c] = True
    
    countDescendants[c][0] = 1 # only c
    
    if(distanceFromRoot[c] >= K): result += 1

    # from u, traverse to u's child nodes
    for v in graph[c]:
        if(visited[v]): continue
        dfs(v, c)
        
        for i = 1 -> K:
            countDescendants[c][i] += countDescendants[v][i - 1]

    # If c is the lca, how many pairs (u, v) with lca = c and dist(u, v) = k there are?
    
    for v1 in graph[c]:
        if(v1 == parent): continue
        for v2 in graph[c]:
            if(v2 == parent || v1 > v2): continue
            ### Consider each pair of two different subbranches of c
            for leftDist = 0 -> k - 2:
                rightDist = k - 2 - leftDist
                #
                result += countDescendants(v1, leftDist) * countDescendants(v2, rightDist)            
        
dfs(1) # 1 is the root

print(result)

=> O(N^2 * K) (worst case là tất cả các node đều là node con của 1)

c) Tối ưu
- Nhận xét: Với mỗi v2 (bên phải), phải xét tất cả các v1 bên trái nó để nhân với countDescendants[v1][]

=> Gom tất cả các v1 bên trái này lại và tính toán với v2 cùng một lúc
=> Mỗi lần đi qua một đỉnh con v của c thì cộng vào countDescendants[c][]

def dfs(c, parent)
    ...
    for v2 in graph[c] & v != parent:
        
        # consider v as "v2" - the right branch
        for rightDist = 0 -> k - 2:
            leftDist = k - 2 - rightDist
            
            # now all the previous subbranch has been accumulated into countDescendants[c]
            result += countDescendants[c][leftDist] * countDescendants[v2][rightDist]
        
        countDescendants[c][] += countDescendants[v2][]
    ...

result = 0

bool visited[N]
int distanceFromRoot[N]
int countDescendants[N][K]
list graph[N] # graph[u] = list of neighbors of u

# dfs function
def dfs(c, parent = 0):
    distanceFromRoot[c] = distanceFromRoot[parent] + 1
    visited[c] = True
    
    if(distanceFromRoot[c] >= K): result += 1

    
    # If c is the lca, how many pairs (u, v) with lca = c and dist(u, v) = k there are?
    # 
    # from c, traverse to u's child nodes
    for v2 in graph[c]:
        if(visited[v2]): continue
        dfs(v2, c)
        
        for rightDist = 0 -> k - 2:
            leftDist = k - 2 - rightDist
            
            # now all the previous subbranch has been accumulated into countDescendants[u]
            result += countDescendants[c][leftDist] * countDescendants[v2][rightDist]
        
        for i = 0 -> K:
            countDescendants[c][i] += countDescendants[v2][i] # not i - 1
            
    # update countDescendants[c][i]
    for i = K - 1 -> 0:
        countDescendants[c][i + 1] = countDescendants[c][i]
    
    countDescendants[c][0] = 1 # only c

dfs(1) # 1 is the root

print(result)

4, Pseudocode

5, Complexity
- O(N * K) (Mỗi v2 chỉ có một parent nên chỉ được tính một lần)