CF2101E 题解

· · 题解

题意

给定一棵 n 个点的树和长为 n 的 01 串 s。称长为 m 的序列 a 合法，当且仅当 a 中元素两两不同，\forall i\in[1,m],a_i\in[1,n],s_{a_i}=1，且 \forall i\in [1,m-2],2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2})，其中 d(u,v) 表示树上 u,v 间简单路径的边数。对于 x\in[1,n] 分别求 a_1=x 时，合法 a 序列的最大长度。n\le 7\times 10^4。

题解

首先看到 2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2}) 可以很自然地注意到每次路径长度至少翻倍，而路径长度不会超过 n-1，因此序列长度不会超过 O(\log n)，或许会对本题有帮助。

之后考虑使用 DP 解决该问题，注意到 DP 状态中只能记录开头或结尾元素，难以限制两两不同。然而仔细考虑 d 的限制后发现，若两次经过点 x，设第二个 x 的前缀为 y，则有 d(y,x)>d(x,p_1)+d(p_1,p_2)+\cdots+d(p_k,y)，然而 d(y,x) 是 y\to x 的唯一最短路径，不可能存在比其长度更短的，因此序列合法时不可能存在相同元素，故可以忽略该限制。

因此 DP 就是可行的了，最朴素的 DP 状态为 f_{x,i,j} 表示 a_1=x，结尾为 i 且最后一条路径长度为 j 的最长合法序列长度。然而容易想到 x 这一维并不必要，可以将最终的序列倒过来考虑，设 f_{i,j} 表示开头为 i，第一条路径长度为 j 的最长合法序列长度，通过在开头加元素来转移，状态数压缩到了 O(n^2)，但还是难以接受。

这时想起答案不会超过 O(\log n)，因此 DP 值不会超过 O(\log n)。考虑将 DP 值和状态互换，显然序列长度相同时第一条路径越长越优。因此设 f_{i,x} 表示开头为 i，长为 x 的合法序列中第一条路径的最大长度，这样状态数就变成 O(n\log n) 的了。

之后考虑转移，f_{j,x+1}\leftarrow d(i,j) 需要满足 2d(i,j)\le f_{i,x}。考虑枚举 x 进行 O(\log n) 轮转移，并使用点分治优化，即在分治中心处转移所有路径经过中心的 (i,j) 对。则 i 转移到 j 的值为 d_i+d_j，有限制 2(d_i+d_j)\le f_{i,x}，拆开得到 2d_i-f_{i,x}\le -2d_j，这里 d_x 为深度。因此以 2d-f 为下标，用树状数组记录前缀 d_i 的最大值即可进行转移。这里需要在点分治处理时正反跑两遍，总时间复杂度 O(n\log^3 n)，分别来自状态数、点分治和树状数组，在 6s 的时限下已经可以通过，代码。

考虑能否优化到 O(n\log^2n)，发现正反跑两遍的过程实际上是把 p_i\ne p_j 的限制拆成了 p_i<p_j 或 p_i>p_j，其中 p_x 表示 x 所在的分治中心子树。如果能将所有子树的信息预处理到一起，查询时快速去掉 p_j 子树内的信息并转移，就能降低复杂度。考虑把上式整个取反为 f_{i,x}-2d_i\ge 2d_j，在每个下标上维护 d 的最大值和所属子树不同的次大值，并预处理出后缀信息。由于最大值和次大值信息合并可以 O(1) 实现，整个后缀处理仍是线性的，查询时取子树外的最大值即可。

注意到查询的 d_j 不会超过 siz_u，因此把超过 2siz_u 的下标上的值均赋到 2siz_u 上即可，数组大小得到保证，总时间复杂度 O(n\log^2n)，代码。由于常数较大，实际并没有比原来快多少。事实上限制式可以整体除以 2，得到 \lfloor \frac{f_{i,x}-2d_i}2\rfloor\ge d_j，可以通过数组大小少个 2 的常数，然而也没快多少，可能是实现得比较粗糙了。