A10812 | Bear and Tree Jumps
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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$ .
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 $a_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=n$ ) — the indices on vertices connected with $i$ -th edge.
It's guaranteed that the given edges form a tree.
The next $n-1$ lines describe edges in the tree. The $i$ -th of those lines contains two integers $a_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=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$ .
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$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted