#1961. 你的互相追逐的头

    ID: 1961 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2578来源:qoj.ac数据:公开样例模拟倍增

你的互相追逐的头

你的互相追逐的头

题目描述

标题: 你的互相追逐的头 - Problem - QOJ.ac

#14584. 你的互相追逐的头

Statistics

那么下面,我将对█████的头是否有独立意识进行测试。

你好,█████的头。

如果看到了这条消息,请回复。

如果看到了这条消息,请回复。

如果看到了这条消息,请回复。

如果看到了这条消息,请回复。

如果看到了这条消息,请回复。

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