← 返回题目列表

Codeforces · 1970/C3

C3. 树上的游戏(困难)

中文机器翻译题面 查看原题

这是问题的困难版本。此版本中唯一的区别是对 $$$t$$$ 的约束。

Ron 和 Hermione 正在一棵由 $$$n$$$ 节点组成的树上玩游戏,这些节点最初是不活动的。游戏由 $$$t$$$ 轮组成,每一轮都从一个节点上的一颗石头开始,该节点被视为已激活。移动包括选择节点上有石头的不活动邻居并将石头移动到那里(从而激活该邻居)。罗恩首先采取行动,然后他与赫敏交替行动,直到没有有效的行动可用。无法采取行动的玩家将输掉这一轮。如果双方都发挥最佳,谁会赢得这场比赛的每一轮比赛?

请注意,所有回合均使用同一棵树进行;仅起始节点发生变化。而且,每轮结束后,所有活跃节点再次被视为不活跃。

输入

第一行包含整数 $$$n$$$ ($$$2 \leq n \leq 2\times 10^5$$$)、$$$t$$$ ($$$1 \leq t \leq n$$$)、树中的节点数和轮数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$1 \leq u, v \leq n$$$,对应于树的一条边。

下一行包含 $$$t$$$ 整数 $$$1 \leq u_1 , \dots , u_t \leq n$$$ ,对应于最初放置石头的节点。

输出

输出由 $$$t$$$ 行组成,每行要么是“Ron”,要么是“Hermione”。

示例

输入 #1

5 2
1 2
1 3
3 4
3 5
1 2

输出 #1

Ron
Ron

输入 #2

6 3
1 2
2 3
1 4
4 5
4 6
1 4 6

输出 #2

Hermione
Ron
Hermione