TopCoder SRM 562 - 1000: InducedSubgraphs

Problem Statement

题目简述

给一棵 n 个结点的树，

定义一个结点集合是连通的表示这棵树以这个集合为点集的导出子图是连通图。

再给一个整数 k ，将树上的结点重新编号，使得对于任意一个满足 1 <= i <= n-k+1 的i

都满足由所有编号在[i,i+k-1]内的结点组成的结点集合是连通的。

问这样的编号方式有多少种。1 <= k <= n <= 41。

Given an undirected graph G and a subset of its vertices S, the subgraph of G induced by S (denoted G/S) is defined as the subgraph of the graph G such that the following two conditions are satisfied:

The set of vertices of the subgraph G/S is exactly S.
For any two vertices x, y in S, there is an edge {x,y} in G/S if and only if there is such an edge in G.

In other words, the induced subgraph always contains all the edges of G it may contain, given its vertices.

In this problem, you are given a tree G containing n vertices and a positive integer k. Initially, the vertices of G are numbered from 0 to n-1, inclusive. The objective is to change this numbering so that all induced subgraphs over {i, i+1, .., i+k-1} are connected, for all 0 <= i <= n-k. How many ways of renumbering are there?

The initial tree G is given as two int[]s edge1 and edge2, each containing n-1 elements. These two int[]s describe the endpoints of edges. For each i, there is an edge between the vertices edge1[i] and edge2[i]. Let C be the number of ways to renumber the vertices that satisfy the condition above. Your method must return (C modulo 1,000,000,009).

Definition

Class InducedSubgraphs
Method getCount
Parameters vector<int> , vector<int> , int
Returns int
Method signature int getCount(vector<int> edge1, vector<int> edge2, int k)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

A tree is a connected graph with no cycles.

Constraints

edge1 will contain between 1 and 40 elements, inclusive.
edge2 will contain the same number of elements as edge1.
Each element of edge1 and edge2 will be between 0 and n-1, inclusive, where n is (the number of elements in edge1) + 1.
A graph represented by edge1 and edge2 will be a tree.
k will be between 1 and n, inclusive.

Test cases

input
- edge1 { 0, 1 }
- edge2 { 1, 2 }
- k 2
output
Returns 2
note
Initially, the graph looks as follows:
```
   0-1-2
```
There are two correct ways to assign the new numbers to its vertices:
```
   0-1-2
```
and
```
   2-1-0
```

input

edge1 { 0, 1, 3 }
edge2 { 2, 2, 2 }
k 3

output

Returns 12

note

The given graph:

     0-2-1
       |
       3

Possible numberings are as follows.

     0-1-2     0-1-3     2-1-3     3-1-2     2-1-0     3-1-0
       |         |         |         |         |         |
       3         2         0         0         3         2

     0-2-3     1-2-3     3-2-1     3-2-0     0-2-1     1-2-0
       |         |         |         |         |         |
       1         0         0         1         3         3

input

edge1 { 5, 0, 1, 2, 2 }
edge2 { 0, 1, 2, 4, 3 }
k 3

output

Returns 4

note

The given graph:

     5-0-1-2-4
           |
           3

Possible ways:

     0-1-2-3-4     0-1-2-3-5
           |             |
           5             4

     5-4-3-2-1     5-4-3-2-0
           |             |
           0             1

input
- edge1 { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 }
- edge2 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
- k 11
output
Returns 481904640
input
- edge1 { 5, 9, 4, 10, 10, 0, 7, 6, 2, 1, 11, 8 }
- edge2 { 0, 0, 10, 3, 0, 6, 1, 1, 12, 12, 7, 11 }
- k 6
output
Returns 800
input
- edge1 { 0, 5, 1, 0, 2, 3, 5 }
- edge2 { 4, 7, 0, 6, 7, 5, 0 }
- k 3
output
Returns 0
input
- edge1 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
- edge2 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
- k 1
output
Returns 890964601

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

back to the menu