CF504E Misha and LCP on Tree 题解

CF504E Misha and LCP on Tree

题意

• 给定一棵 $n$ 个节点的树，每个节点有一个小写字母。
• 有 $m$ 组询问，每组询问为树上 $a \to b$ 和 $c \to d$ 组成的字符串的最长公共前缀。
• $n \le 3 \times 10^5$，$m \le 10^6$。

题解

首先，根据 hash 值具有可减性，可以通过预处理每个点到根以及根到每个点的 hash 值，$\mathcal O(1)$ 求出任意一条没有拐点的路径的 hash 值。

考虑树剖，我们可以将 $a \to b$ 和 $c \to d$ 的路径分别拆成 $\mathcal O(\log n)$ 个区间，然后每次消掉一个区间。

如果消不掉这个区间，则在这个区间上二分找到答案。

总时间复杂度 $\mathcal O(n + m \log n)$。

另外，在 CF 上最好写双 hash，且不能采用自然溢出，否则大概率被卡。

代码

#define Hash pair <modint, modint>

const int N = 3e5 + 7, mod = 1e9 + 7;
const Hash B = mp((modint)131, (modint)13331);
int n, m, d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
Hash p[N], h1[N], h2[N];
char c[N];
vi e[N];

inline Hash operator + (Hash a, Hash b) {
	return mp(a.fi + b.fi, a.se + b.se);
}

inline Hash operator - (Hash a, Hash b) {
	return mp(a.fi - b.fi, a.se - b.se);
}

inline Hash operator * (Hash a, Hash b) {
	return mp(a.fi * b.fi, a.se * b.se);
}

inline Hash H(bool o, int x, int k) {
	if (o) return h2[x-k+1] - h2[x+1] * p[k];
	return h1[x+k-1] - h1[x-1] * p[k];
}

void dfs(int x) {
	s[x] = 1;
	for (auto y : e[x])
		if (y != f[x]) {
			f[y] = x, d[y] = d[x] + 1, dfs(y), s[x] += s[y];
			if (s[y] > s[son[x]]) son[x] = y;
		}
}

void dfs(int x, int p) {
	top[x] = p, dfn[x] = ++num, rnk[num] = x;
	if (son[x]) dfs(son[x], p);
	for (auto y : e[x]) if (y != f[x] && y != son[x]) dfs(y, y);
}

inline int lca(int x, int y) {
	while (top[x] != top[y]) {
		if (d[top[x]] > d[top[y]]) swap(x, y);
		y = f[top[y]];
	}
	if (d[x] > d[y]) swap(x, y);
	return x;
}

inline vector <pi> get(int x, int y) {
	int z = lca(x, y);
	vector <pi> o, w;
	while (d[top[x]] > d[z]) o.pb(mp(x, top[x])), x = f[top[x]];
	o.pb(mp(x, z));
	while (d[top[y]] > d[z]) w.pb(mp(top[y], y)), y = f[top[y]];
	if (y != z) w.pb(mp(son[z], y));
	while (w.size()) o.pb(w.back()), w.pop_back();
	return o;
}

int main() {
	rd(n), rds(c, n), p[0] = mp(1, 1), p[1] = B;
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x), p[i+1] = p[i] * B;
	d[1] = 1, dfs(1), dfs(1, 1);
	for (int i = 1; i <= n; i++)
		h1[i] = h1[i-1] * B + mp(c[rnk[i]], c[rnk[i]]),
		h2[n+1-i] = h2[n+2-i] * B + mp(c[rnk[n+1-i]], c[rnk[n+1-i]]);
	rd(m);
	while (m--) {
		int a, b, c, d, ans = 0;
		ui s = 0, t = 0;
		rd(a), rd(b), rd(c), rd(d);
		vector <pi> f = get(a, b), g = get(c, d);
		while (s < f.size() && t < g.size()) {
			int df1 = dfn[f[s].fi], df2 = dfn[f[s].se];
			int dg1 = dfn[g[t].fi], dg2 = dfn[g[t].se];
			bool of = df1 > df2, og = dg1 > dg2;
			int lf = (of ? df1 - df2 : df2 - df1) + 1;
			int lg = (og ? dg1 - dg2 : dg2 - dg1) + 1;
			int len = min(lf, lg);
			Hash hf = H(of, df1, len);
			Hash hg = H(og, dg1, len);
			if (hf == hg) {
				if (len == lf) ++s;
				else f[s].fi = rnk[df1+(of?-1:1)*len];
				if (len == lg) ++t;
				else g[t].fi = rnk[dg1+(og?-1:1)*len];
				ans += len;
			} else {
				int l = 1, r = len;
				while (l < r) {
					int mid = (l + r) >> 1;
					hf = H(of, df1, mid);
					hg = H(og, dg1, mid);
					if (hf == hg) l = mid + 1;
					else r = mid;
				}
				ans += l - 1; break;
			}
		}
		print(ans);
	}
	return 0;
}