• [1635] Explosion

  • 时间限制: 10000 ms 内存限制: 65535 K
  • 问题描述
  • there is a country which contains n cities connected by n - 1 roads(just like a tree). If you place TNT in one city, all the roads connect these city will be destroyed, now i want to destroy all the roads with the least number of TNT, can you help me ?

  • 输入
  • Input starts with an integer T(T <= 500), denoting the number of test case.
    For each test case, first line contains n(1 <= n <= 1000), denoting the number of cities, next n - 1lines following and each line contains two different cities denoting these two cities connect directly. You can assume the input guarantee the relation among cities is a tree.
  • 输出
  • For each test case, print the least number of TNT that i need to destroy all the n - 1 roads.
  • 样例输入
  • 2
    5
    1 2
    2 3
    3 4
    4 5
  • 样例输出
  • 2
  • 提示
  • 来源
  • Alex@NBUT
  • 操作

显示春菜