CF771C.Bear and Tree Jumps
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 .
输入格式
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.
输出格式
Print one integer, denoting the sum of f(s,t) over all pairs of vertices (s,t) such that s<t .
输入输出样例
输入#1
6 2 1 2 1 3 2 4 2 5 4 6
输出#1
20
输入#2
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
输出#2
114
输入#3
3 5 2 1 3 1
输出#3
3
说明/提示
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 .