Casinos and travel

题意翻译

【题目描述】 给定一棵节点数为 n 的树，树的各节点上你可以安排一些陷阱。 已知函数 f(t)表示这棵树的顶点为 t，每次任意选择一条一段是根节点一段是叶子节点的链走到头，不管怎么走走到头后会遇见偶数个陷阱，你在树上所安排陷阱的方案数。 求∑ f(i) （1<=i<=n） 【输入描述】 第一行输入一个数 n(1 ≤ N ≤ 100000)，表示树的节点数。 接下来 n-1 行，每行两个符合条件的数 a,b，表示节点 a,b 之间有边相连。 【输出描述】 输出一个数∑ f(i) （mod 10^9+7） 【样例解释】 F(1)：(0,0,0) (1,0,1) (1,1,0) (0,1,1) F(2)：(0,0,0) (1,1,1) F(3)：(0,0,0) (1,0,1) (1,1,0) (0,1,1)

题目描述

John has just bought a new car and is planning a journey around the country. Country has $ N $ cities, some of which are connected by bidirectional roads. There are $ N-1 $ roads and every city is reachable from any other city. Cities are labeled from $ 1 $ to $ N $ . John first has to select from which city he will start his journey. After that, he spends one day in a city and then travels to a randomly choosen city which is directly connected to his current one and which he has not yet visited. He does this until he can't continue obeying these rules. To select the starting city, he calls his friend Jack for advice. Jack is also starting a big casino business and wants to open casinos in some of the cities (max $ 1 $ per city, maybe nowhere). Jack knows John well and he knows that if he visits a city with a casino, he will gamble exactly once before continuing his journey. He also knows that if John enters a casino in a good mood, he will leave it in a bad mood and vice versa. Since he is John's friend, he wants him to be in a good mood at the moment when he finishes his journey. John is in a good mood before starting the journey. In how many ways can Jack select a starting city for John and cities where he will build casinos such that no matter how John travels, he will be in a good mood at the end? Print answer modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

In the first line, a positive integer $ N\ (1<=N<=100000) $ , the number of cities. In the next $ N-1 $ lines, two numbers $ a,\ b\ (1<=a,b<=N) $ separated by a single space meaning that cities $ a $ and $ b $ are connected by a bidirectional road.

输出格式

Output one number, the answer to the problem modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

4

输入样例 #2

3
1 2
2 3

输出样例 #2

10

说明

Example 1: If Jack selects city 1 as John's starting city, he can either build 0 casinos, so John will be happy all the time, or build a casino in both cities, so John would visit a casino in city 1, become unhappy, then go to city 2, visit a casino there and become happy and his journey ends there because he can't go back to city 1. If Jack selects city 2 for start, everything is symmetrical, so the answer is 4. Example 2: If Jack tells John to start from city 1, he can either build casinos in 0 or 2 cities (total 4 possibilities). If he tells him to start from city 2, then John's journey will either contain cities 2 and 1 or 2 and 3. Therefore, Jack will either have to build no casinos, or build them in all three cities. With other options, he risks John ending his journey unhappy. Starting from 3 is symmetric to starting from 1, so in total we have $ 4+2+4=10 $ options.