পাইথনে ট্রি থেকে দূরত্ব ঠিক k হয় এমন ভিন্ন ভের্টেক্স জোড়ার সংখ্যা বের করুন

সমস্যা বিবরণ

একটি ইন্টিজার k এবং n নোডযুক্ত একটি ট্রি দেওয়া আছে। দূরত্ব ঠিক k হয় এমন ভিন্ন ভের্টেক্স জোড়ার সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, k=2 এবং নিচের ট্রি হলে আউটপুট 4।

সমাধানের ধাপসমূহ

1. N = 5005, এডজেসেন্সি লিস্ট graph, ২D অ্যারে vertex_count[505][5005], res=0।
2. insert_edge(x,y) দিয়ে এজ যোগ করুন।
3. dfs(v, parent):
   • vertex_count[v][0] = 1।
   • প্রতিটি চাইল্ড i জন্য:
     • dfs(i, v)।
     • j = 1 থেকে k পর্যন্ত: res += vertex_count[i][j-1] * vertex_count[v][k-j]।
     • j = 1 থেকে k পর্যন্ত: vertex_count[v][j] += vertex_count[i][j-1]।
4. dfs(1, 0) কল করুন এবং res প্রিন্ট করুন।

পাইথন কোড উদাহরণ

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

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

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

k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)
dfs(1, 0)
print(res)  # আউটপুট: 4

ইনপুট

k = 2 insert_edge(1, 2) insert_edge(2, 3) insert_edge(3, 4) insert_edge(2, 5)

আউটপুট

4