主页
练习
竞赛
分类
状态
排名
问答
Login
Problem5423--最小步数(step)
5423: 最小步数(step)
Time Limit:
1.000 Sec
Memory Limit:
128 MB
Submit:
25
Solved:
4
[
Submit
] [
Status
] [
Web Board
] [Creator:
]
Description
给你一个度为K的N个点的树，或者说，每个点至多有K个儿子。这棵树是“最低能量”的：这些点当且仅
当上一层排满以后，才会在这一层从左往右排。这些点的序号也是有序的，从1开始。比如有：
你需要输出Q个询问的答案，形式是x y，表示询问从点x走到点y的最小步数是多少。
Input
第一行包含三个整数N,K,Q（N<=10^15,1<=K<=1000,1<=Q<=100000）
接下来Q行，每行两个整数x,y（1<=x,y<=N,x≠y）
Output
共Q行，一行一个答案。
Sample Input
7 2 3 1 2 2 1 4 7
Sample Output
1 1 4
HINT
【样例解释】
样例1中，1与2是相邻的，4->2->1->3->7
【数据范围】
20%：1<=N,Q<=1000
50%：1<=N,Q<=100000
100%：N<=10^15,1<=K<=1000,1<=Q<=100000
Source/Category
[
Submit
] [
Status
]