นับคู่โหนดใน Tree ที่มีระยะห่างเท่ากับ k ใน Python

นับคู่โหนดระยะห่าง k ใน Tree

กำหนด Tree n โหนด และจำนวนเต็ม k นับจำนวนคู่โหนด (u,v) ที่ระยะห่าง (จำนวนขอบบน Path) เท่ากับ k อย่างแน่นอน

อัลกอริทึม Tree DP (DFS)

• dp[v][d] = จำนวนโหนดใน Subtree ของ v ที่ห่างจาก v เป็น d
• DFS Post-order: รวม dp จากลูกเข้ามาแม่
• เมื่อประมวลผลลูก u ของ v:
  • นับคู่ที่ผ่าน v: Σ dp[u][j-1] * dp[v][k-j] สำหรับ j=1..k
  • อัปเดต dp[v][j] += dp[u][j-1]

โค้ดตัวอย่าง Python

N = 5005
graph = [[] for _ in range(N)]
dp = [[0]*505 for _ in range(N)]
res = 0

def add_edge(x, y):
    graph[x].append(y)
    graph[y].append(x)

def dfs(v, parent):
    global res
    dp[v][0] = 1
    for u in graph[v]:
        if u != parent:
            dfs(u, v)
            for j in range(1, k+1):
                res += dp[u][j-1] * dp[v][k-j]
            for j in range(1, k+1):
                dp[v][j] += dp[u][j-1]

k = 2
add_edge(1,2); add_edge(2,3); add_edge(3,4); add_edge(2,5)
dfs(1, 0)
print(res)  # 4