A
一棵树,\(q\) 次询问,每次给定 \(x,d_x,y,d_y\),你需要找到一个 \(u\) 使得 \(dis(u,x)=d_x,dis(v,x)=d_y\)。
\(n,q\le 1e6\)。
稍微转化为对于点 \(k\),找到一个距离为 \(d\) 的点,使得不走 \(x,y\) 这边子树。
只需要求出每个点距离最远的几个点,且位于不同子树。
因为要是存在距离 \(k\) 点 \(t(t>d)\) 的点,那么距离 \(d\) 的点势必也存在。
两次 dp。第一遍求出子树内前三远的点,第二遍换根加上走父亲那条边的贡献。
B
\(n\) 个点 \(m\) 条边的无向图,你需要求所有导出子图中只有一个连通块的个数取模 \(2\)。
\(n\le50\),每条边 \(|u-v|\le 12\)。
利用取模 \(2\) 的性质,设一个导出子图联通块个数为 \(s\),如果令其贡献为 \(2^s\bmod 4\),
那么若最后 \(\bmod 4\) 为 \(2\),就是 \(1\),否则是 \(0\)。
\(2^s\) 有很好的性质,也就是把导出子图黑白染色,每个连通块只有一种颜色点的方案数。
于是我们可以设计状态 \(f_{i,j}\) 表示当前处理到第 \(i\) 个点,前 \(12\) 个点的状态(黑/白/不选)。
转移只需枚举 黑/白/不选 即可。
C
给定长度为 \(n\) 的字符串,取出其所有长 \(m\) 的子串,求每个子串有多少与其相似的。
相似是最多只有一个位置不同。\(m\le n\le 1e5\)
S,T 相似,等价于 \(\text{LCP}(S,T)+\text{LCS}(S,T)\ge m-1\)。
考虑建出原串的前缀树和后缀树,每个子串都能分别对应前后缀树上的一个点,两个串的 \(\text{LCP}\) 就是这两个串所对应的点在前缀树上的 LCA 的深度,\(\text{LCS}\) 同理。
那么就是对每个点 \(u\),求有多少个点 \(v\) 满足 \(dep1[lca1(u,v)]+dep2[lca2(u,v)]≥m-1\)。
在第一棵树上做 dsu on tree,加入一个点 \(u\) 时,可以知道 \(dep1[lca1(u,v)]\), 那么只要求有多少个点满足它与 \(u\) 在第二棵树上的 LCA 的深度 \(≥m-1-dep1[lca1(u,v)]\),就是求 \(u\) 往根路径上的深度最小且满足上述要求的点的子树中,有多少个点在第一棵树中被 dsu 到。
考虑用树状数组维护每个点在第二棵树上的 dfs 序,那么它就是一个单点加区间查。
但是这样只能算出有多少对 \(u,v\) 满足 \(dep1[lca1(u,v)]+dep2[lca2(u,v)]\ge 2m-1\)。
再用一棵树状数组维护当前被 dsu 到的节点的答案,跟上一棵树状数组相反,这个要支持区间加,单点查。这样就成功解决了本题。复杂度 \(O(n \log^2n)\)。