看到异或求和，考虑拆位计算 $v+d(c,x)$ 的第 $k$ 位。不难发现它随着 $d(c,x)$ 每增大 $2^k$ 改变一次。
这启示我们对于每个点考察它对所有祖先的贡献。于是我们要做的第一步是树上差分，将一系列深度相差 $2^k$ 的祖先的差分值异或 $1$。
这个操作不能暴力做。考虑用一个桶对于每个 $i$ 记录某个点的所有祖先中，深度 $\bmod2^k=i$ 的点的差分值。但是这样子树需要向父亲贡献一个合并复杂度为 $O(s)$（$s$ 表示子树大小）或 $O(2^k)$ 的信息，取决于考虑子树内每个点对桶的贡献，还是直接使用子树的桶在对应位置相加。前者可以用树上启发式合并优化。
更好的做法是维护子树内可减信息的经典 trick（天天爱跑步）：
维护一个全局桶，子树跟处只需要记录自己关心的某个位置的值，在遍历子树前和遍历子树后的差，即可求得子树内对桶该位置的贡献。
对于每个子树，显然下端点不在子树内的链不会对子树内部的覆盖情况产生影响，所以我们将所有下段点在子树内的链构的集合的一个能够完全覆盖该子树的子集称作一种合法方案；将一种合法方案的下段点最靠上的链称作最浅链。
我们要对于每颗子树的每种可能的最浅链取值，维护权值最小的合法方案。
儿子转移向父亲的过程中，需要加入答案最小的以下段点为儿子的链为最浅链的方案。此时贪心地选择子树内维护的所有合法方案中答案最小者，加上该链贡献即可。
多个儿子合并时，如果某条链被钦定为父亲答案中的最浅链，除了该链下段点所在的儿子子树，其余儿子子树中贪心选择所有合法方案中最小值即可。如果其余子树中的方案选择使得该链最终不是最浅链，这样构造出来的错误方案一定不优于钦定真实的最浅链为最浅链构造出来的方案，所以无关紧要。
于是我们需要这样一种数据结构：能够快速求出集合中最小值，快速给集合权值整体加 $k$，合并若干集合。因此使用可并堆。
至于在转移过程中不能完全覆盖子树而变得不合法的方案，可以 lazy 地进行弹出。即使用到某个集合最小值时再判断其合法性，不合法则弹出。
首先设 $f_i$ 为从 $1$ 跳到 $i$ 的最小花费，$O(n^2)$ DP 是简单的。
观察性质。首先，如果 $a_k\le a_j,a_k\le a_i$，那么 $i\to j$ 的转移一定是不优于 $i\to k\to j$ 的。
其次，考察 $j\to i$ 的转移，若 $i-j\ge\frac n{a_i}$，那么有 $a_i(i-j)^2\ge(i-j)n$，也即该转移不优于 $j\to j+1\to\cdots\to i-1\to i$。
所以只需从前往后遍历每个位置 $i$，向前枚举 $j$，直到 $a_j\le a_i$ 或 $i-j\le\dfrac n{a_i}$，进行 $j\to i$ 的转移；再向后枚举 $j$，直到 $a_j\le a_i$ 或 $j-i\le\frac n{a_i}$，进行 $i\to j$ 的转移即可。
上述两个性质分别保证了两种优化的正确性，现在来证明其复杂度。
对于不超过 $\sqrt n$ 的数，最多有 $O(\sqrt n)$ 种，每个数向前向后枚举遇到相同数就会停止，所以每一种数带来的的总复杂度为 $O(n)$。
对于超过 $\sqrt n$ 的数 $a_i$，向前/向后枚举的次数为 $\frac n{a_i}\le\sqrt n$。
综上，总复杂度为 $O(n\sqrt n)$。
将该组合游戏进行拆解，某个 DAG 上该游戏先手必胜等价于 $1,2$ 节点的 SG 值不相等。
某个节点的 SG 值为其所有后继节点的 $\mathrm{mex}$，也即某个节点的 SG 值为 $x$ 当且仅当其向 SG 值分别为 $[0,x)$ 的节点各连了至少一条边，并且没有连向 $x$ 的边。
这提示我们从小到大，每次考察 SG 值为 $x$ 的点的集合。SG 值大于 $x$ 的所有节点必须向这个集合中至少连一条边；这个集合中的节点不能向集合中其它节点连边；SG 值小于 $x$ 的所有节点连边无限制。
状压 DP 即可。
设初始局面只有点 $x$ 被染色，最后被染色的点集为 $f(x)$，那么显然起初有多个点 $x_1,x_2,\cdots,x_m$ 染色，最终被染色的点集为 $f(x_1)\cup f(x_2)\cup\cdots\cup f(x_m)$。
于是我们探寻 $f(x)$ 会包含哪些节点。
对于点 $i<x$，它被染色当且仅当存在点 $j$ 不在 $x$ 左侧，并且满足 $V_j<V_i$。这样 $i$ 要么先与 $x$ 相遇，被染色；要么先与 $j$ 相遇，此时 $j$ 一定在 $x$ 左侧，即 $j$ 一定被染色，于是 $i$ 被染色。显然不存在其它染色情况。
同理，对于点 $i>x$ 它被染色当且仅当存在点 $j$ 不在 $x$ 右侧，并且满足 $V_j>V_i$。
我们把所有点按照 $X$ 排序后重新编号。设 $\mathrm{pmx}_i=\max_{i\in[1,i]}V_i$ 和 $\mathrm{smn}=\min_{i\in[i,n]}V_i$。于是 $f(x)=\{i\mid i<x\land V_i<\mathrm{smn_i}\}\cup\{i\mid i>x\land V_i>\mathrm{pmx_i}\}\cup\{x\}$。
于是考虑对初始局面进行 DP。设 $g_i$ 为最靠右的初始被染色的点，且能够最终将 $[1,i]$ 中所有点都染上色的初始局面数。
那么由 $g_j$ 到 $g_i$ 的转移只需要保证 $(i,j)$ 中所有节点都染上色即可，即 $(i,j)$ 中不存在点 $t$ 使得 $V_t\in[\mathrm{pmx}_j,\mathrm{smn}_i]$。考虑到 $\mathrm{pmx},\mathrm{smn}$ 均单调，可以使用双指针维护。
考虑到序列的后缀颜色数随着后缀长度增加单调不减，而非空区间内的颜色数只可能有 $1,2,3$ 种，所以尝试维护后缀颜色数出现差异的左端点位置，即从右向左第一次出现新颜色的位置、第二次出现新颜色的位置。
对前缀 $[1,i]$ 进行 DP，校验所有右端点为 $i$ 的限制，对符合限制的状态向后贡献即可。
所有人按照 $l$ 从小到大排序，依次尝试匹配从左到右每一个凳子。如果当前考虑到第 $i$ 个人，在尝试匹配从左到右第 $j$ 个凳子，且不满足 $j\le l_i$，此时 $[1,i]$ 中至少有一个人需要选择满足 $j\ge r_i$ 的凳子 $j$，显然在这些人中选择 $r_i$ 最小者一定不劣。
左侧匹配完，再把所有第一步未匹配的点按照 $r_i$ 从大到小排序，然后类似地贪心匹配。
正确性大概来源于，匈牙利算法可以以任意顺序遍历每个尚未被匹配的点，以任意顺序遍历一个点的所有出边。
第二种做法，先用运用霍尔定理的推论，将题意转化为，选择多条线段，求线段条数加线段交的长度最大值。
枚举线段交的左端点 $l$，此时能够选取的线段的左端点一定 $\le l$。此时对于该点右侧的每个点 $r$，它作为线段交的右端点的答案是 $r-l+k$，其中 $k$ 为完全包含 $[l,r]$ 区间的线段数量。
于是给线段树上每个点 $i$ 赋初始权值 $i$，把线段按照左端点从小到大排序，依次枚举线段 $[l,r]$，在线段树上给 $[l,r]$ 区间加一，求 $[l,+\infty)$ 区间最大值即可。
将答案序列看作一条平面上由 $(n,m)$ 到 $(0,0)$ 的路径，某次答案为 Yes 则往左走，否则往下走。于是每道题都与某条边一一对应；而每次答题人所面对的状态，即目前两种答案分别剩 $x,y$ 个，则与平面上某个点 $(x,y)$ 一一对应。
那么答题人的最优策略是显然的，当目前在直线 $y=x$ 以下时，猜答案为 Yes；当目前在直线 $y=x$ 以上时，猜答案为 No；当恰好落在直线上时，随便怎么猜，猜对的概率均为 $\frac12$。
我们来考察某种答案序列所对应的路径，假设 $n\ge m$，将整条路径在所有 $x=y$ 点处断开，形成多个段。
$n>m$ 时第一个段一定在 $y=x$ 下，这个段中每次询问都会得到回答 Yes，其中所有向左走的路径对应的问题是正确的，于是这段中答对问题的数量等于这部分路径的 $x$ 坐标跨度。
其余段中，除了段首第一个询问恒定有 $\frac12$ 的概率是正确的，其余所有边朝向直线 $y=x$ 的问题都是回答正确的。而这些段中起点终点均在 $y=x$ 上，所以 $x$ 坐标跨度等于 $y$ 坐标跨度，所以这些段中回答正确的问题数量期望都等于 $x$ 坐标跨度加 $\frac12$。
于是总答案等于 $n+\frac k2$，其中 $k$ 为回答的第二类段的期望数量，等于该路径与直线 $y=x$ 的交点个数减一。
那么对于每个点 $(x,x)$ 计算路径经过它的概率，计算相应贡献即可。
首先，可以自由排序等价于可以任意交换满足 $a_i>a_{i+1}$ 的 $i,i+1$，于是等价于任意重排后保持原有顺序对不交换。
那么从前往后枚举 $t$ 中的每个字符，在保证不与已匹配的字符中小于它的冲突的基础上，贪心地匹配 $s$ 尽量靠前者即可。
首先，将一个斐波那契数写成两个斐波那契数之和的方案是唯一的。
并且不难发现将一棵大小为斐波那契数的数划分为两个大小为斐波那契数的子树，最多只有两种方案。
我们来证明，如果 Fib-tree 有两种划分方案，那么这两种划分方案都可以划出两个 Fib-tree 来，也即我们可以任意决策。
考察其中一种能够划出两个 Fib-tree 的划分方案，称两个子树中较大者为 $A$，较小者为 $B$，显然另一种方案中，断开的边落在 $A$ 中，并且 $A$ 照这条边断开后仍然能形成两个 Fib-tree，所以原树按照这条边断开后亦能形成两个 Fib-tree。得证。
所以暴力寻找要割开的边即可。