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 nn vertices, numbered 11 through nn .

Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most kk .

For a pair of vertices (s,t)(s,t) we define f(s,t)f(s,t) as the minimum number of jumps Limak needs to get from ss to tt . Your task is to find the sum of f(s,t)f(s,t) over all pairs of vertices (s,t)(s,t) such that s<t .

输入格式

The first line of the input contains two integers nn and kk ( 2<=n<=2000002<=n<=200000 , 1<=k<=51<=k<=5 ) — the number of vertices in the tree and the maximum allowed jump distance respectively.

The next n1n-1 lines describe edges in the tree. The ii -th of those lines contains two integers aia_{i} and bib_{i} ( 1<=ai,bi<=n1<=a_{i},b_{i}<=n ) — the indices on vertices connected with ii -th edge.

It's guaranteed that the given edges form a tree.

输出格式

Print one integer, denoting the sum of f(s,t)f(s,t) over all pairs of vertices (s,t)(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 66 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 22 . For example, from the vertex 55 he can jump to any of vertices: 11 , 22 and 44 (well, he can also jump to the vertex 55 itself).

There are pairs of vertices (s,t)(s,t) such that s<t . For 55 of those pairs Limak would need two jumps: (1,6),(3,4),(3,5),(3,6),(5,6)(1,6),(3,4),(3,5),(3,6),(5,6) . For other 1010 pairs one jump is enough. So, the answer is 52+101=205·2+10·1=20 .

In the third sample, Limak can jump between every two vertices directly. There are 33 pairs of vertices (s<t) , so the answer is 31=33·1=3 .

首页