Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n-1 edges, and each edge is 1 unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps:

1. Choose a node, x, from the tree.
2. Cut a subtree consisting of all nodes which are not further than r units from node x .

For example, the blue nodes in the diagram below depict a subtree centered at x=1 that has radius r=2:

Given n, r, and the definition of Jenny's tree, find and print the number of different subtrees she can cut out. Two subtrees are considered to be different if they are not isomorphic.

Input Format

The first line contains two space-separated integers denoting the respective values of n and r. Each of the next n-1 subsequent lines contains two space-separated integers x, and y, describing a bidirectional edge in Jenny's tree having length 1 .

Constraints

• 1 n 3000
• 0 r 3000
• 1 x,y n

Subtasks

For 50% of the max score:

• 1 n 500
• 1 r 500

Output Format

Print the total number of different possible subtrees.

Sample Input 0

7 1

1 2

1 3

1 4

1 5

2 6

2 7

Sample Output 0

3

Explanation 0

In the diagram below, blue nodes denote the possible subtrees:

The last 5 subtrees are considered to be the same (i.e., they all consist of two nodes connected by one edge), so we print 3 as our answer.

Sample Input 1

7 3

1 2

2 3

3 4

4 5

5 6

6 7

Sample Output 1

4

Explanation 1

In the diagram below, blue nodes denote the possible subtrees:

Here, we have four possible different subtrees.

****************************Complete the code correctly according to the instructions given.******************************

#include

using namespace std;

string ltrim(const string &);

string rtrim(const string &);

vector split(const string &);

/*

* Complete the 'jennysSubtrees' function below.

*

* The function is expected to return an INTEGER.

* The function accepts following parameters:

* 1. INTEGER n

* 2. INTEGER r

* 3. 2D_INTEGER_ARRAY edges

*/

int jennysSubtrees(int n, int r, vector> edges) {

}

int main(){

ofstream fout(getenv("OUTPUT_PATH"));

string first_multiple_input_temp;

getline(cin, first_multiple_input_temp);

vector first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);

int r = stoi(first_multiple_input[1]);

vector> edges(n - 1);

for (int i = 0; i < n - 1; i++) {

edges[i].resize(2);

string edges_row_temp_temp;

getline(cin, edges_row_temp_temp);

vector edges_row_temp = split(rtrim(edges_row_temp_temp));

for (int j = 0; j < 2; j++) {

int edges_row_item = stoi(edges_row_temp[j]);

edges[i][j] = edges_row_item;

} }

int result = jennysSubtrees(n, r, edges);

fout << result << " ";

fout.close();

return 0;

}

string ltrim(const string &str) {

string s(str);

s.erase(

s.begin(),

find_if(s.begin(), s.end(), not1(ptr_fun(isspace)))

);

return s;

}

string rtrim(const string &str) {

string s(str);

s.erase(

find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base(),

s.end()

);

return s; }

vector split(const string &str) {

vector tokens;

string::size_type start = 0;

string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {

tokens.push_back(str.substr(start, end - start));

start = end + 1;

}

tokens.push_back(str.substr(start));

return tokens;

}

Answer rating: 100% (QA)

The problem is about finding the different unique subtrees that can be extracted by taking each node ... View the full answer