[UVa] 13274 - Christmas Tree

題目

Link: UVa 13274 - Christmas Tree

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 沒有指定方向,
沒有說左邊的是 parent 右邊的是 child 。

程式碼

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[1001];

  // 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[1].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;
}

Show Comments