[USACO10JAN] Cow Telephones G

题目描述

The cows have set up a telephone network, which for the purposes of this problem can be considered to be an unrooted tree of unspecified degree with N (1 <= N <= 100,000) vertices conveniently numbered 1..N. Each vertex represents a telephone switchboard, and each edge represents a telephone wire between two switchboards. Edge i is specified by two integers A\_i and B\_i the are the two vertices joined by edge i (1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i). Some switchboards have only one telephone wire connecting them to another switchboard; these are the leaves of the tree, each of which is a telephone booth located in a cow field. For two cows to communicate, their conversation passes along the unique shortest path between the two vertices where the cows are located. A switchboard can accomodate only up to K (1 <= K <= 10) simultaneous conversations, and there can be at most one conversation going through a given wire at any one time. Given that there is a cow at each leaf of the tree, what is the maximum number of pairs of cows that can simultaneously hold conversations? A cow can, of course, participate in at most one conversation. ```cpp 1 5 C1 C5 | | || || 2---4 --> |2---4| | | || || 3 6 C3 C6 ``` Consider this six-node telephone tree with K=1: There are four cows, located at vertices 1, 3, 5 and 6. If cow 1 talks to cow 3, and cow 5 talks to cow 6, then they do not exceed the maximum number of conversations per switchboard, so for this example the answer is 2 (for two pairs of cows talking simultaneously). 奶牛们要建立一个电话网络,它们可以被认为是一个无根树(大概是个图吧。。。),里面N (1 <= N <= 100,000)个结点可以简便的编号为1...N。每一个结点代表一个电话交换机(类似开关),每条边代表一个连接两个电话交换机的电话线。边i是用两个整数A\_i和B\_i表示的,也就是该边连接着A\_i和B\_i两个电话交换机(1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i). 一些电话交换机只有一根电话线;它们是这棵树的叶子结点,每个叶子结点只有一只牛。当两头牛在通话时,它们的对话沿着唯一的在两头牛所在结点的最短路径。 一个电话交换机只能忙于K(1 <= K <= 10)个同时的对话,而且每个电话线同一时间只能传送一个对话。 给出一个每个叶子结点都有一头牛的树, 问最多有多少对奶牛能在同一时间进行它们的对话?

输入输出格式

输入格式


\* Line 1: Two space separated integers: N and K \* Lines 2..N: Line i+1 contains two space-separated integers: A\_i and B\_i

输出格式


\* Line 1: The number of pairs of cows that can simultaneously hold conversations

输入输出样例

输入样例 #1

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

输出样例 #1

2