#BZOJ4281. Związek Harcerstwa Bajtockiego
-
ID: 2878
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Związek Harcerstwa Bajtockiego
No submission language available for this problem.
题目描述
给定一棵有n个点的无根树，相邻的点之间的距离为1，一开始你位于m点。之后你将依次收到k个指令，每个指令包含两个整数d和t，你需要沿着最短路在t步之内（包含t步）走到d点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。
输入格式
第一行包含三个正整数n,m,k(1<=m<=n<=1000000,1<=k<=1000000)。
接下来n-1行，每行包含两个正整数x,y(1<=x,y<=n)，描述一条树边。
接下来k行，每行两个整数d,t(1<=d<=n,0<=t<=10^9)，描述一条指令。
输出格式
输出一行，包含k个正整数，即执行每条指令后你所在的位置。
3 1 2
1 2
2 3
3 4
1 1
3 2