February 24, 2018

# 題目

13274 Christmas Tree

Christmas is coming and Bob wants to decorate his tree. The tree has N nodes. 1 is the root. He thinks a tree is beautiful if each node has exactly K child (immediate descendant) nodes (of course except the leaf nodes). He wants to remove zero or more nodes of the tree so that the property holds. If we delete a non-leaf node, the whole subtree rooted in that node, will be removed from the tree. What is the maximum number of nodes the tree can have after deleting some (possibly zero) nodes so that it has the above properties?

Input

The first line contains T (1 ≤ T ≤ 1000) , number of test cases. For each test case, the first line contains two space-separated integers N ( 1 ≤ N ≤ 1000) and K (1 ≤ K ≤ 100) . Each of the next N −1 lines contains two integers U and V (1 ≤ U, V ≤ N), denoting an edge.

Output

For each case, print the case number and the answer.

Sample Input

2
6 3
1 2
1 3
1 4
4 5
4 6
6 4
1 2
1 3
1 4
4 5
4 6


Sample Output

Case 1: 4
Case 2: 1


## Hint

test case 輸入的 edge 沒有指定方向，

# 程式碼

## C++

#include <algorithm>
#include <iostream>
#include <vector>

int answer(std::vector<int>*const& tree, int max_subs, int from, int node);
inline int answer(std::vector<int>*const& tree, int max_subs)
{ return answer(tree, max_subs, 0, 1); }

int main()
{
// variables for storing number of test cases and current test case
int test_cases, test_case;

// variables for storing number of nodes to the tree and maximum number of children to each node
int nodes, max_subs;

// variables for storing where the edge linked to
int edge1, edge2;

// variable for for loop
int i;

// although it says this is a tree, it can't be build in a normal way
// the best way to store it is to make it like a graph(but it's still a tree)
// and the number 1001 is the maximum number was declared by the problem
// use to decrease memory allocation overhead
std::vector<int> tree;

// disable synchronization with C's library
std::ios::sync_with_stdio(false);

// read number of test cases from stdin
std::cin >> test_cases;

// running test cases
for (test_case = 1; test_case <= test_cases; ++test_case)
{
// read the number of nodes to a tree and max number of children to each node
std::cin >> nodes >> max_subs;

for (i = 1; i <= nodes; ++i) tree[i].clear();

// make the root node has (children + 1) links
tree.push_back(0);

// a loop for read the tree
for (i = 1; i < nodes; ++i)
{
// read edges from stdin
std::cin >> edge1 >> edge2;

// since they didn't specified the direction of every links
tree[edge1].push_back(edge2);
tree[edge2].push_back(edge1);
}

// output the answer of current test case
std::cout << "Case " << test_case << ": "
<< answer(tree, max_subs) << std::endl;
}

// done. nothing goes wrong
return 0;
}

// use a recursive way to find the answer
// like BFS method of graphs
int answer(std::vector<int>*const& tree, int max_subs, int from, int node)
{
// -1 since every node contains a link that links to its parent
auto node_subs = static_cast<int>(tree[node].size()) - 1;

// if the number of children less than requirement then drop them
if (node_subs < max_subs) return 1;

std::vector<int> subs(static_cast<uint64_t>(node_subs));
int i = 0, loop = node_subs - max_subs;

// include the current node
int result = 1;

// find out how many nodes that each sub nodes can contains(inclusive)
for (auto child : tree[node])
if (child != from) subs[i++] = answer(tree, max_subs, node, child);

// find out the maximum number
std::sort(subs.begin(), subs.end());
for (i = node_subs - 1; i >= loop; --i) result += subs[i];

return result;
}