C-牛牛染颜色_牛客练习赛62

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。

每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。

求一共有多少种好的染色的方案。

即：求树上有多少个点集 $S$ 对于 $\forall i,j\in S,i\neq j$ 满足： $\operatorname{lca}(i,j)\in S$ 。
答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

第一行一个整数 ，表示这棵树有  个节点。
接下来  行，每行两个整数  表示  之间有一条边。

一行一个整数，表示所有合法的点的集合数量。

示例1

复制

复制


共计14个集合满足题意。
注意：空集也算进答案里面！

示例2

复制

复制