حل تمرین اکبر جوجه کوئرا با پایتون

حل تمرین اکبر جوجه کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین اکبر جوجه کوئرا با پایتون

یک درخت n راسی به شما داده می‌شود. مجموعه P (که می‌تواند تهی شود) از رئوس درخت را اکبرجوجه می‌نامیم، اگر برای هر دو عضو متمایز u و v در P، هیچ یک از u یا $v$ جد دیگری نباشد. می‌گوییم راس u جد راس v است اگر در مسیر v به راس 1، راس u قرار بگیرد. هدف پیدا کردن باقی‌مانده تعداد زیرمجموعه‌های اکبرجوجه از رئوس درخت بر 10⁹ + 7 است، این عدد را در خروجی چاپ کنید.

ورودی

در خط اول ورودی عدد $n$ که به شما داده می‌شود که بیانگر تعداد رئوس گراف است. سپس در n−1 خط، و در خط iام، دو عدد u_i​ و v_i​ می‌آید که به معنی یالی بین این دو راس است. تضمین می‌شود گراف ورودی درخت است.

خروجی

در تنها خط خروجی باقی‌مانده تعداد زیرمجموعه‌های اکبرجوجه درخت را بر 10⁹ + 7 چاپ کنید.

مثال

ورودی نمونه 1

4
1 2
2 3
3 4

خروجی نمونه 1

5

شرح ورودی و خروجی نمونه شماره یک: مجموعه موردنظر حداکثر می‌تواند شامل یک راس شود که خود چهار حالت دارد و یک حالت هم مجموعه تهی است، پس پاسخ برابر پنج است.

ورودی نمونه 2

4
1 2
1 3
1 4

خروجی نمونه 2

9

کد پایتون سوال تمرین جعبه شکلات

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

MOD = int(1e9 + 7)
N = int(1e5 + 10)
root = 1

adj = defaultdict(list)
dp = [0] * N

def dfs(v, p=-1):
    w = 1
    for u in adj[v]:
        if u == p:
            continue
        dfs(u, v)
        w *= dp[u]
        w %= MOD
    w += 1
    w %= MOD
    dp[v] = w

n = int(input())
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

dfs(root)
print(dp[root])

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.