[CF2013F2] Game in Tree

不知道是算好牛还是好不牛的题

题意

现在有一棵个点的树，初始时 Alice 在点，Bob 在点。

两个人轮流进行操作，Alice 先手。每一个人操作的时候需要走向当前点的一个邻居，并且这个邻居之前没有被两个人访问过，不能走的人输。

给定两个点，对路径链上的每一个点求出答案，保证不在的路径上。

。

先来考虑如何对于一个固定点求出答案。

首先将到路径上面所有的点拿出来，假设他们分别是，满足且。我们称这些点为关键点。

然后考虑这个游戏的过程，首先肯定是两个人都在这些关键点上，朝对面的方向走。

直到有一个人某步走在了一个非关键点上，之后两个人会往尽可能远的地方走，第一个走不了的人输。

特别的，如果两个人直到最后都没有走到非关键点上，则可以通过奇偶性判断谁赢。

设表示从点出发，不经过其他的关键点，能走出的最长简单路径有多长。

假设当前 Alice 在点上，Bob 在点上，现在该 Alice 走了，考虑什么情况下 Alice 会走到非关键点上。

此时若 Alice 下一步要往非关键点上走，那么 Alice 还最多能走步。

后面 Bob 会挑选尽可能远的地方走，那么 Bob 最多还能走步。

由于下一步是 Alice 走，所以当时，Alice 必胜，时，Alice 必败。

换句话说，若时，Alice 会走到非关键点上，此时 Alice 必胜，否则 Alice 会继续往前走到。

Bob 的策略同理。

考虑模拟这个过程，中间求区间最值的操作可以使用两个 st 表完成。

那么就可以在复杂度求出单个点的答案

其实求区间最值的过程可以看成每一次删一个数字，然后求最大值，可以直接拿一个桶存起来，然后每一次从上一次查询的答案往下扫，这样就可以做到了，不过这不重要。

F1 的代码，复杂度是的（这份代码我写的时候序列是反过来写的）。

然后来考虑 F2 怎么做。

考虑求出和这两条路径上所有答案，这两条链上的点包含了路径上所有点。

假设当前想要求路径上所有点答案（同理），还是一样先把路径上点拿出来，从到分别是。

考虑这么一个事情，根据上面的讨论，两个人一定是能往非关键点上走就一定往非关键点上走，也就是说，如果我们能求出，两个人最早能在哪个位置往非关键点上走，问题就解决了。

设表示当 Bob 起点为时，Alice 最早在点上往非关键点走。同理。

那么问题在于如何求出和。以举例。

考虑枚举一个点，看一下 Bob 的起点为哪些点时，Alice 从走出去会必胜。

假设当前有两个点，满足（是因为需要当 Alice 走到点时 Bob 还没有撞上去）。

如果 Bob 的起点是，并且此时 Alice 从走出去必胜，那么可以发现，若 Bob 的起点是，则 Alice 从走出去一定也必胜。

为什么呢？根据上面的讨论，起点为时，Bob 还能走次。

而起点为时，Bob 还能走。

而因为，所以一定有，也就是说，点能贡献到的是一个区间（为什么左端点是呢，因为小于两个人就撞了）。

而这个我们是可以直接二分出来的。

所以可以直接枚举每一个，二分出其贡献的区间，然后用线段树（我代码中用的一个类似 st 表的东西）做区间覆盖（或者取最大值，都可以），就能直接算出了。

每一个点对的贡献也是一段区间，可以自己推，不细说了。

然后是有一些细节：

代码在这里，太长了贴出来好丑。

~~我也是没想到一个博弈题怎么代码这么长。~~