ได้รับรายการขอบ edges ที่เป็นต้นไม้ (Tree) สำหรับแต่ละขอบ ต้องหาจำนวนเส้นทางที่ไม่ซ้ำกัน (unique paths) ที่ผ่านขอบนั้น โดยคืนค่าเป็นลิสต์ตามลำดับขอบในอินพุต
ตัวอย่าง
edges = [[0,1], [0,2], [1,3], [1,4]]
0
/ \
1 2
/ \
3 4
ผลลัพธ์: [6, 4, 4, 4]
แนวทางแก้ปัญหา
ข้อสังเกตสำคัญ: จำนวนเส้นทางที่ผ่านขอบ (u, v) = size(u) × size(v) โดยที่ size(x) คือจำนวนโหนดในสับต้นไม้ที่รากคือ x เมื่อตัดขอบนั้นออก
- สร้าง Adjacency List
- DFS คำนวณขนาดสับต้นไม้
count[node]สำหรับทุกโหนด - สำหรับขอบ
(a, b): ให้x = min(count[a], count[b])คำตอบคือx × (n - x)
การใช้งาน (Python)
from collections import defaultdict
class Solution:
def solve(self, edges):
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
count = defaultdict(int)
def dfs(node, parent):
count[node] = 1
for nei in adj[node]:
if nei != parent:
count[node] += dfs(nei, node)
return count[node]
dfs(0, -1)
n = count[0]
ans = []
for a, b in edges:
x = min(count[a], count[b])
ans.append(x * (n - x))
return ans
# ทดสอบ
ob = Solution()
edges = [[0,1], [0,2], [1,3], [1,4]]
print(ob.solve(edges)) # Output: [6, 4, 4, 4]
ความซับซ้อน
- Time Complexity: O(N)
- Space Complexity: O(N)
