求调教喵求调教喵求调教喵 WA on #6

有时答案会少一

#include <bits/stdc++.h>

using namespace std;

namespace liuzimingc {
#define pii pair<int, int>
#define endl '\n'
#define int long long

const int N = 3e5 + 5, P = 13331, MOD = 1e9 + 7;
 
int n, m, dep[N], d[N], fa[N][20], son[N], top[N], lg[N], p[N], dfn[N], cnt, inv[N];
int f[N][20];
int hash1[N], hash2[N];
char s[N];
vector<int> e[N], up[N], down[N];

int get_min(int u, int v) {
	return dfn[u] < dfn[v] ? u : v;
}

int lca(int u, int v) {
	if (u == v) return u;
	int l = dfn[u], r = dfn[v];
	if (l > r) swap(l, r);
	l++;
	int len = lg[r - l + 1];
	return get_min(f[l][len], f[r - (1 << len) + 1][len]);
}

void dfs1(int u, int fa) {
    d[u] = dep[u] = dep[fa] + 1;
    hash1[u] = (hash1[fa] * P + s[u]) % MOD;
    hash2[u] = (hash2[fa] + s[u] * p[dep[u] - 1]) % MOD;
    liuzimingc::fa[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; i++)
        liuzimingc::fa[u][i] = liuzimingc::fa[liuzimingc::fa[u][i - 1]][i - 1];
    for (int v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        if (d[v] > d[u]) d[u] = d[v], son[u] = v;
    }
}

void dfs2(int u, int fa, int t) {
	f[dfn[u] = ++cnt][0] = fa;
    top[u] = t;
    if (u == t) {
        for (int i = 0, x = u; i <= d[u] - dep[u]; i++, x = liuzimingc::fa[x][0])
            up[u].push_back(x);
        for (int i = 0, x = u; i <= d[u] - dep[u]; i++, x = son[x])
            down[u].push_back(x);
    }
    if (!son[u]) return;
	dfs2(son[u], u, t);
    for (const int &v : e[u]) {
        if (v == son[u] || v == fa) continue;
        dfs2(v, u, v);
    }
}

int ask_fa(int x, int k) {
    if (!k) return x;
    x = fa[x][lg[k]];
    k -= 1 << lg[k];
    k -= dep[x] - dep[top[x]];
    x = top[x];
    return k >= 0 ? up[x][k] : down[x][-k];
}

int get_hash(int u, int v) { // hashing of u -> v
	if (u == v) return s[u];
	if (dep[u] < dep[v]) {
		return (hash1[v] - hash1[fa[u][0]] * p[dep[v] - dep[fa[u][0]]] % MOD + MOD) % MOD;
	}
	else {
		return (hash2[u] - hash2[fa[v][0]] + MOD) % MOD * inv[dep[v] - 1] % MOD;
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    cin >> n >> (s + 1);
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	p[0] = 1;
	auto qkpow = [&](int a, int b) {
		int ans = 1;
		while (b) {
			if (b & 1) ans = ans * a % MOD;
			a = a * a % MOD;
			b >>= 1;
		}
		return ans;
	};
	inv[0] = 1;
	inv[1] = qkpow(P, MOD - 2);
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] * P % MOD;
		inv[i] = inv[i - 1] * inv[1] % MOD; 
	}
    dfs1(1, 1);
    dfs2(1, 1, 1);
    for (int j = 1; (1 << j) <= n; j++)
    	for (int i = 1; i + (1 << j) - 1 <= n; i++)
    		f[i][j] = get_min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    cin >> m;
    while (m--) {
    	int a, b, c, d;
    	cin >> a >> b >> c >> d;
    	if (s[a] != s[c]) {
    		cout << 0 << endl;
    		continue;
		}
    	int l1 = lca(a, b), l2 = lca(c, d);
    	int l = 1, r = min(dep[a] + dep[b] - dep[l1] * 2, dep[c] + dep[d] - dep[l2] * 2) + 1;
    	static auto calc = [&](int u, int v, int l, int k) {
    		if (k <= dep[u] - dep[l] + 1) return get_hash(u, ask_fa(u, k - 1));
			k -= dep[u] - dep[l] + 1;
			int t = ask_fa(v, dep[v] - dep[l] - 1);
    		return (get_hash(u, l) * p[k] % MOD + get_hash(t, ask_fa(v, dep[v] - dep[l] - k))) % MOD;
		};
    	static auto check = [&](int mid) {
    		return calc(a, b, l1, mid) == calc(c, d, l2, mid);
		};
    	while (l < r) {
    		int mid = l + r + 1 >> 1;
    		if (check(mid)) l = mid;
    		else r = mid - 1;
		}
		
		cout << l << endl;
	}
	return 0;
}
#undef int
}

int main() {
//	freopen("01.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	liuzimingc::main();
    return 0;
}