4350: Bear and Tree Jumps熊和树跳跃
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：4
通过：4
题目描述
C. Bear and Tree Jumps
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
利马克是一只小北极熊。他住在一棵由n个顶点组成的树中，编号为1到n。
利马克最近学会了跳。他最多可以从一个顶点跳到距离k以内的任何顶点。
对于一对顶点（s， t） 我们定义f（s， t） 因为Limak需要从s到t的最小跳跃次数。您的任务是找到f（s， t） 在所有顶点对（s， t） 这样 s < t。
A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.
Limak is a little polar bear. He lives in a tree that consists of n vertices, numbered 1 through n.
Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most k.
For a pair of vertices (s,t) we define f(s,t) as the minimum number of jumps Limak needs to get from s to t. Your task is to find the sum of f(s,t) over all pairs of vertices (s,t) such that s<t.
Input
The first line of the input contains two integers n and k (2≤n≤200000, 1≤k≤5)− the number of vertices in the tree and the maximum allowed jump distance respectively.The next n-1 lines describe edges in the tree. The i-th of those lines contains two integers ai and bi (1≤ai,bi≤n)− the indices on vertices connected with i-th edge.
It's guaranteed that the given edges form a tree.
Output
Print one integer, denoting the sum of f(s,t) over all pairs of vertices (s,t) such that s<t.
Examples
Input
6 2 1 2 1 3 2 4 2 5 4 6
Output
20
Input
13 3 1 2 3 2 4 2 5 2 3 6 10 6 6 7 6 13 5 8 5 9 9 11 11 12
Output
114
Input
3 5 2 1 3 1
Output
3
Note
In the first sample, the given tree has 6 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 2. For example, from the vertex 5 he can jump to any of vertices: 1, 2 and 4 (well, he can also jump to the vertex 5 itself).
There are 
pairs of vertices (s,t) such that s<t. For 5 of those pairs Limak would need two jumps: (1,6),(3,4),(3,5),(3,6),(5,6). For other 10 pairs one jump is enough. So, the answer is 5·2+10·1=20.In the third sample, Limak can jump between every two vertices directly. There are 3 pairs of vertices (s<t), so the answer is 3·1=3.
输入格式
输入的第一行包含两个整数n和k（2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5） -树中的顶点数和最大允许跳跃距离。
接下来的n-1行描述树中的边。这些行中的第i行包含两个整数ai和bi(1 ≤ ai, bi ≤ n)-与第i条边连接的顶点上的索引。
保证给定的边形成一棵树。
接下来的n-1行描述树中的边。这些行中的第i行包含两个整数ai和bi(1 ≤ ai, bi ≤ n)-与第i条边连接的顶点上的索引。
保证给定的边形成一棵树。
输出格式
打印一个整数，表示f（s， t） 在所有顶点对（s， t） 使得s＜t。
输入样例 复制
6 2
1 2
1 3
2 4
2 5
4 6输出样例 复制
20