本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-14 21:33:09

题意

给定一棵 $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$ 的常数，然而也没快多少，可能是实现得比较粗糙了。