题目描述

陈太阳有一棵树。这棵树一共有 $n$ 个节点,$n−1$ 条边。陈太阳用他的太阳之力给在每个点上设置了一个开关。当他按下点 $x$ 的开关后,与 $x$ 相连的边都会消失,与 $x$ 不相邻的点都会向 $x$ 连一条边。(即与 $x$ 相邻的边的存在性被取反)。陈太阳决定选择一个点集,并按下这些点的开关。他想知道,有多少种选择方法使得按下开关后最终的图是联通的。方案可能有很多,你只需要输出答案除以 $1000000007$ 的余数。

输入格式

本题有多组测试数据。第一行一个整数 $T$,表示测试数据的个数。每个测试数据内:

第一行一个正整数 $n$ 表示树的节点数。接下来 $n−1$ 行,每行三个整数 $x,y$,表示 $x$ 与 $y$ 之间有一条边。保证输入是一棵树。

输入格式

输出一行一个整数,表示答案模 $1000000007$。

思路

将原问题转化为黑白染色,将连接不同颜色的点的边的存在性反转。发现不连通的情况很少,考虑计算不连通的方案数。

代码