题目 2205: # Cleaning Robots(L)

时间限制: 3s
内存限制: 320MB 提交: 8 解决: 2

The new ICPC town has N junctions (numbered from 1 to N) which are connected by N−1 roads. It is possible from one junction to go to any other junctions by going through one or more roads. To make sure all the junctions are well-maintained, the government environment agency is planning to deploy their newest advanced cleaning robots. In addition to its cleaning ability, each robot is also equipped with a movement ability such that it can move from one junction to any other junctions connected by roads. However, as you might have guessed, such robots are not cheap. Therefore, the agency is considering the following deployment plan.

Let Tk be the set
of junctions which should be cleaned by the kth robot (also known as, the robot's task), and |Tk|≥1 be the number of junctions in Tk. The junctions
in Tk form
a **path**, i.e. there exists a sequence of v1,v2,…,v|Tk| where vi∈Tk and vi≠vj for all i≠j such that
each adjacent junction in this sequence is connected by a road. The union
of T for all robots is equal to the set of all junctions
in ICPC town. On the other hand, no two robots share a common junction,
i.e. Ti∩Tj=∅ if i≠j.

To avoid
complaints from citizens for an inefficient operation, the deployment plan
should be *irreducible*; in other words, there should be no two
robots, i and j, such
that Ti∪Tj forms a (longer) path. Note that the agency does
not care whether the number of robots being used is minimized as long as all
the tasks are irreducible.

Your task in this problem is to count the number of feasible deployment plan given the town's layout. A plan is feasible if and only if it satisfies all the above-mentioned requirements.

For example, let N=6 and the roads are {(1,3),(2,3),(3,4),(4,5),(4,6)}. There are 5 feasible deployment plans as shown in the following figure.

· The first plan uses 2 robots (labeled as A and B in the figure) to clean {1,2,3} and {4,5,6}.

· The second plan uses 3 robots (labeled as A, B, and C in the figure) to clean {1,3,4,6}, {2}, and {5}.

· The third plan uses 3 robots to clean {1,3,4,5}, {2}, and {6}.

· The fourth plan uses 3 robots to clean {1}, {2,3,4,6}, and {5}.

· The fifth plan uses 3 robots to clean {1}, {2,3,4,5}, and {6}.

No other plans are feasible in this case. For example, the plan {{1,3},{2},{4,5,6}} is not feasible as the task {1,3} and {2} can be combined into a longer path {1,3,2}. The plan {{1,2,3,4},{5},{6}} is also not feasible as {1,2,3,4} is not a path.

Input begins with a line containing an integer: N (1≤N≤100000) representing the number of junctions. The next N−1 lines each contains two integers: uiui vivi (1≤ui<vi≤N) representing a road connecting junction ui and junction vi. It is guaranteed that it is possible from one junction to go to any other junctions by going through one or more roads.

Output in a line an integer representing the number of feasible deployment plans. As this output can be large, you need to modulo the output by 1000000007.

6 1 3 2 3 3 4 4 5 4 6

5