#1961. 你的互相追逐的头
你的互相追逐的头
你的互相追逐的头
题目描述
标题: 你的互相追逐的头 - Problem - QOJ.ac
#14584. 你的互相追逐的头
那么下面,我将对█████的头是否有独立意识进行测试。
你好,█████的头。
如果看到了这条消息,请回复。
如果看到了这条消息,请回复。
如果看到了这条消息,请回复。
如果看到了这条消息,请回复。
如果看到了这条消息,请回复。
uzjandgh aidokahquxjensgkandvxhandbgsnwbegsbsbwvhzbsbwhdhdhttp://███.███.███.███/problem/███bdhbeyzhXbakxokcngehdnDbekzjycwjwjd
题面描述
某天,某棵树上的你的若干个头想做一个游戏。
具体来说,你有一棵 n 个节点的树,接下来你的头会在这棵树上做 m 次游戏:
一次游戏里,会有你的 k 个头参与,分别在 x1,x2,⋯,xk 的位置,为了选手的精神健康着想,保证 xi 互不相同
你的每个头都有它最喜欢的一个头,你惊奇的发现,你的第 i 个头最喜欢的头恰好是你的第 (imodk)+1 个头。每时每刻,所有头都会朝着它们最喜欢的头的方向以 1 条边每单位时间的速度运动,注意运动是连续的。
现在,在一旁旁观的你的第 k+1 个头想要知道游戏进行的怎么样,你的第 k+1 个头会向你提出 q 次询问,每次询问给定 p,t,你需要告诉它你的第 p 个头在第 t 时刻处在哪个位置(可能在边上,见输出格式)。
不同游戏之间 k,q 可能不同,并且游戏之间相互独立。
一些移动的细节:
- 如果一个头和它最喜欢的头重合,那么你可以认为它之后都会一直跟着它喜欢的头移动。
- 如果所有头聚在一个点上,那么所有头保持不动。
输入格式
第一行两个整数 n,m,表示树的大小,以及游戏数。
接下来 n−1 行每行两个整数 u,v,表示节点 u 和 v 之间存在一条边。
接下来依次描述 m 个游戏:
第一行两个正整数 k,q,表示头的数量以及询问数。
第二行 k 个整数 x1,x2,⋯,xk,表示头的初始位置。
接下来 q 行每行两个整数 p,t,描述每个询问。
输出格式
对于每个情景,输出 q 行,依次回答每个询问。
如果头的位置在点 u 上,请输出 u u(用空格分隔),如果头的位置在边 u−v 上,设 u<v,请输出 u v(用空格分隔)。
样例 #1
样例输入
10 2
7 6
1 4
10 7
9 2
5 7
3 7
10 9
8 6
4 10
3 2
10 2 3
1 2
1 1
4 4
9 1 8 5
4 1
3 2
3 3
1 999999993
样例输出
10 10
9 9
7 7
7 7
7 10
7 10
数据范围
对于所有数据,2≤n≤2×105,2≤k≤n,1≤q≤2×105,∑k,∑q≤4×105,1≤t≤109。
subtask 1(13 pts):n≤3000,∑k≤6000,请注意并未对 q 做出任何保证。
subtask 2(8 pts):树的形态随机,随机方式为初始随机一个排列 a1,a2,⋯,an,然后对于每个 ai(2≤i≤n),从 a1,a2,⋯,ai−1 中随机选择一个连向 ai。
subtask 3(14 pts):保证树是一条链。请注意不保证这条链的编号依次为 1∼n。
subtask 4(8 pts):k=3。
subtask 5(8 pts):k=4。
subtask 6(17 pts):k≤30。
subtask 7(16 pts):n≤105,∑k≤2×105。
subtask 8(16 pts):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
10 2
7 6
1 4
10 7
9 2
5 7
3 7
10 9
8 6
4 10
3 2
10 2 3
1 2
1 1
4 4
9 1 8 5
4 1
3 2
3 3
1 999999993
10 10
9 9
7 7
7 7
7 10
7 10