P11471 时空轮回 题解

zrl123456 · 2025-11-23 10:39:50 · 题解

:::::info[题目基本信息]{open} 考察：贪心，哈希 Hashing，STL，离线处理（省选/NOI-）。
题目简介：
给定一棵树，有 n 个结点，以 1 为根，每个点有点权，q 次询问，每次询问给定序列 \{s_{len}\}，设 ans_i 为 1 到 i 的简单路径上所有点的点权按顺序排列构成的序列最多能划分成的部分数使得每部分中都包含 \{s_{len}\} 子串（下文简称匹配），求 \displaystyle\max_{i=1}^nans_i 的值。保证 len 的总和不超过 10^5。
数据范围：

• 1\le n,q,len\le 10^5
• \forall i\in[1,n],1\le a_i\le n
• \forall i\in[1,len],1\le s_i\le n

  ::::: 先考虑一个序列和另一个序列匹配的答案怎么求，有一个显然的贪心，就是从左往右扫，能匹配就匹配，感性理解正确性成立，可以归纳证明。
  那么我们先考虑暴力，对于每个串都 DFS 一遍，对于每个节点都贪心地看以它为末尾的子串能否匹配（这个可以使用哈希实现，预处理维护每个节点到根的序列哈希即可），可以匹配就从 len 级祖先转移过来，否则就从父亲转移，精细实现可以做到 \Theta(qn)。
  我们观察得到每一个串，与它匹配的节点数并不多，因为以每一个节点结尾的长度为定长的字符串是唯一的，这启发我们把询问离线下来，考虑对于每一个长度分别考虑，先通过并查集等方式将询问串相同的询问合并，然后使用 map 存储每个串对应的编号，然后开两个数组 f 和 g 分别表示编号为定值的答案和上一个转移的点是什么，这样我们就可以判断一个点能否更新了，更新时再把答案也一并更新，只需要 DFS 一遍同时回溯就可以处理了。
  常数较大，需要卡常，精细实现可以通过本题。
  时间复杂度为 \Theta(n\sqrt V\log q)（V 为 len 的值域），空间复杂度为 \Theta(n+q+V)。

code