Day 1 ： https://gmoj.net/senior/#contest/home/3355
Day 2 ： https://gmoj.net/senior/#contest/home/3356
两天都考得不好，都只有 25 25 25 分。
先看题，觉得 T 1 T1 T1 有两个性质：
但是我以为步数存在 “借用” 的情况：即假设 Alice 一开始比 Bob 领先 k k k 步。对于一个棋子，即便它在运动的过程中会造成暂时的 Alice 被 Bob 领先，只要这个步数小于 k k k （也就是这个时候 Alice 还是比 Bob 领先的），都可以继续动。如果最后让 Alice 比 Bob 领先更多步数，这个方案是可以被选择的。
结果这样设 DP 状态就要多设一个 “可预支” 步数，转移比较复杂，没弄出来。
最后打了个分类水部分分的程序，没想到爆零了。
T 2 T2 T2 不知道怎么做，就拿了前两个 Subtask 的分。
T 3 T3 T3 看不懂题，盲猜答案，挂了。
最后只有 T 2 T2 T2 的 25 25 25 分。
T 1 T1 T1 想拿前两个 Subtask ，第一个暴力，第二个哈希，但是第二个打挂了。
T 2 T2 T2 前 20 % 20\% 20% 显然直接暴力枚举每个函数的取值就好了嘛，Subtask3 应该要用到一些数学方法（然而 Subtask3 分开枚举就行了）。
结果跑出来只有
5
5
5 分。原因是我忘记在处理新的数据编号时清空前向星 fir 数组了……
T 3 T3 T3 觉得 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4 可以直接 O ( n 2 ) O\left(n^2\right) O(n2) 跑最长路， 5 , 6 5,6 5,6 显然就是树上跳 LCA 嘛。
但是打完之后发现 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4 不能最长路做，这时才意识到这是 xor \operatorname{xor} xor 操作，不能直接取 max \max max 。
于是只有 10 10 10 分。
最后得分： 10 + 5 + 10 = 25 10+5+10=25 10+5+10=25 。
这两天比赛一开始都很困，要注意休息（所以省选前夜就 10 : 00 10:00 10:00 睡觉吧）。
虽然我比较菜，不会切题，但是主要还是算法问题。省选前要把半生不熟的算法都过一遍，尤其注意算法的应用。
即便切不了题，也要努力拿部分分。代码失误率一定要降低！！！
步数是不存在 “借用” 情况的，因为在操作过程中已经有人输掉了。
具体来说，就是假设现在 Alice 在根节点处，如果存在 “借用” 步数的情况的话，她会选择走到 3B 上。但是如果 Bob 在其它棋子的博弈中没有亏步数，他是不会选择在 3B继续往下走的；如果 Bob 已经亏步数了，他往下走只是苟活一步，要输了。所以 Alice 会选择节点 2W 。
那么设 f i f_i fi 表示如果 i i i 上有一个棋子，并且 i i i 归属的玩家先手，能比对手最多领先多少步。
转移就是
f
i
=
max
{
0
,
1
+
max
i
→
j
f
j
,
c
i
=
c
j
1
−
min
i
→
j
f
j
,
c
i
≠
c
j
f_i=\max \begin{cases} 0,\\ 1+\max_{i\to j} f_j, &c_i=c_j\\ 1-\min_{i\to j} f_j, &c_i\neq c_j \end{cases}
fi=max⎩⎪⎨⎪⎧0,1+maxi→jfj,1−mini→jfj,ci=cjci=cj
然后再做一个背包就好了。
用 分块 做。
每次将每个块上的点都暴力跳是不行的，只跳那些不在块中其它点的子树内的点就行了。
这样做要 O ( 1 ) O(1) O(1) 求出任意点的 k k k 级祖先。这是 长链剖分 的经典应用：
先求出每个点的 2 i 2^i 2i 级祖先以及每个长链顶点的距离为 [ 1 , l e n ] [1,len] [1,len] 的祖先（ l e n len len 表示长链长度）。
若 k = 2 t + k ′ ( 2 t ≤ k < 2 t + 1 ) k=2^t +k'(2^t \le k<2^{t+1}) k=2t+k′(2t≤k<2t+1) ，那么先跳到这个点的 2 t 2^t 2t 级祖先（记为 x x x ）处，在 x x x 的祖先上找就可以了。
证明： k ′ < 2 t ≤ l e n k'<2^t\le len k′<2t≤len 。
但是由于所有人的常数都有亿点点大（或者说是题目的时间限制太紧了），OJ 上 3 s 3s 3s 没有人跑得过。
LZC：看到这种字符串问题第一想法就是广义后缀自动机。
建一个 AC自动机 即可，然后把它的 fail树 建出来。
根据 fail指针 的定义：
状态 u u u 的 fail 指针指向另一个状态 v v v ，其中 v ∈ Q v\in Q v∈Q ，且 v v v 是 u u u 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。——OI Wiki
在 字典树 上，某个点的祖先和它的前缀一一对应；在 fail树 上，某个点是它的子树中的每个点的后缀。
因此设 f i f_i fi 表示选择 i i i 作为最后一句话的最大权值。
那么从 1 1 1 到 n n n 枚举每个串，在它的前缀中取 max \max max ，然后把它的 f f f 拿来更新以它为后缀的所有串。
因为 S S S 是 T T T 的字串等价于 S S S 是 T T T 的某个前缀的某个后缀，因此这样做是对的。
真的傻了，上一年暑假我才切过一道类似的题，当时还写了题解的（https://blog.csdn.net/huangzihaoal/article/details/108738867），居然现在又不会做了，看来是对这类题的精髓领悟不深。
发现 ∑ r i − l i + 1 \sum r_i-l_i+1 ∑ri−li+1 比较小，可以暴力网络流。
我们可以对于每个函数 f i ( x i ) f_i (x_i) fi(xi) ，都建一条路径： S → A i , l i → A i , l i + 1 → ⋯ → A i , r i − 1 → A i , r i → T S\to A_{i,l_i}\to A_{i,l_i +1}\to \cdots \to A_{i,r_i -1}\to A_{i,r_i}\to T S→Ai,li→Ai,li+1→⋯→Ai,ri−1→Ai,ri→T 。其中 A i , j A_{i,j} Ai,j 没有实质的含义，但是它向后一个点连的边的流量是有意义的，表示 x i = j x_i=j xi=j 时的代价。由于这个函数必须被选择， S → A i , l i S\to A_{i,l_i} S→Ai,li 的流量为 + ∞ +\infty +∞ 。
先不考虑 m m m 组限制。由于 最大流 = 最小割 ，求出来的就是最小的代价。但是我们这道题要计算的是最大值啊！可以令代价= P − f i ( x i ) P-f_i (x_i) P−fi(xi) ，其中 P P P 是一个很大的数，可以把这个东西加成正数。
对于第 i i i 组限制，令 x u i ≤ x v i + D i x_{u_i}\le x_{v_i}+D_i xui≤xvi+Di 的含义就是：如果 x u i ≥ x x_{u_i}\ge x xui≥x ，那么 x v i ≥ x − D i x_{v_i}\ge x -D_i xvi≥x−Di ，也就是如果 f u i f_{u_i} fui 不选择 [ l u i , x − 1 ] [l_{u_i},x-1] [lui,x−1] ，那么 f v i f_{v_i} fvi 必定只能在 [ x − D , r v i ] [x-D,r_{v_i}] [x−D,rvi] 中选择。因此连若干条 A u i , x → A v i , x − D A_{u_i,x}\to A_{v_i,x-D} Aui,x→Avi,x−D 的边（注意，当 x − D > r v i x-D>r_{v_i} x−D>rvi 时， A u i , x A_{u_i,x} Aui,x 要向 T T T 连边），由于这些限制关系不可以被去除，边权为 + ∞ +\infty +∞ 。
最后跑最大流就好啦！至此和上面那道题基本相同。
等等，那无解怎么判断？
用 差分约束 。 x u ≤ x v + D x_u\le x_v+D xu≤xv+D 这种限制看上去很像最短路的 d i s u ≤ d i s v + l e n ( u , v ) dis_u\le dis_v + len_{(u,v)} disu≤disv+len(u,v) （ d i s dis dis 表示最短路长度， l e n len len 表示边权），因此就从 v v v 向 u u u 连一条边权为 D D D 的边。
至于 x i ∈ [ l i , r i ] x_i\in [l_i,r_i] xi∈[li,ri] 的限制，就一开始先让每个点卡到上界，即 d i s i = r i dis_i=r_i disi=ri 。这样求出来的就是一组尽可能大的解，若此时 d i s i < l i dis_i<l_i disi<li ，说明无解。
有不少人直接判断答案是否超过合理区间，以此判断是否无解。但是这种方法的是错的，因为可能会出现一条链上割掉两条流量不同的边，而不是不得不选择边权为 + ∞ +\infty +∞ 的边的情况。
