这是问题的困难版本。此版本中唯一的区别是对 $$$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