Bài tập tin học[Bài tập luyện quy hoặc động] anime thế giới hòa bình

Đề bài:

Chuyện là Sơn senpai ảo tưởng mình được isekai đến một thế giới toàn loli và làm thần ở thế giới đó, vì mong muốn thống trị của bản thân Sơn đã có một kế hoạch đó là biến thế giới này thành một thế giới hòa bình mà không có chiến tranh nhằm đảm bảo Sơn có nhiều loli nhất có thể ( ͡° ͜ʖ ͡°), và để làm được việc đó, sơn phải phân chia lại vùng đất của 2 vương quốc lớn đó là Betty, Reggy để sao cho 2 vuông quốc này không chiếm lẫn nhau. Thần sơn nhận ra rằng nếu bất kỳ thành phố của vương quốc nào không được kết nối với ít nhất một thành phố đồng mình khác thì thành phố đó sẽ bị chiếm bởi vương quốc kẻ thù. Bài toán này đối với một thằng wibu như Sơn thì không có gì khó nhưng Sơn đang muốn tuyển nhân viên để nghiên cứu máy tính lượng cho Sơn. Vì thế bạn! Tôi nói bạn đó, người đang đọc bài này, Sơn yêu cầu bạn tìm số cách phân chia cho các vùng đất trên. Biết rằng các thành phố kết nối với nhau và tạo thành một Cây

Input

Dòng đầu tiên ghi số nút (n)
(n-1) dòng tiếp theo ghi các kết nối giữa 2 nút

Output

Một số duy nhất là số cách phân chia vùng đất trên, vì giá trị có thể rất lớn nên bạn chỉ cần mod cho (10^9 + 7)

Limits

Time limit: 1 seconds per test set.
Memory limit: 1GB.
Thuật toán ngây thơ (40%) :
2 ≤ n ≤ 20
1 ≤ u,v ≤ n

Test set 2 (60%):
2 ≤ n ≤ 10^5
1 ≤ u,v ≤ n

Sample

Input

5
1 2
1 3
3 4
3 5

Output

4

Minh họa 4 trường hợp thỏa mãn:

Hướng dẫn giải

Quy hoạch động dp[now][cur][ally], trong đó now là nút xét hiện tại, cur là thành phố của vương quốc nào (1, 0), ally là đồng minh hay kẻ thù. code mẫu ở dưới

Code full => csloj