Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n-1 edges, and each
Question:
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:
- Choose a node, x, from the tree.
- 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;
}
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi