CF504E Misha and LCP on Tree

Solution
1197 Words

题目大意

给你一棵有$n$个节点的树，每个节点上有一个字符$c$。

有$m$次询问，每次询问$a\sim b$路径上的字符串和$c \sim d$路径上的字符串的最长公共前缀$\texttt{(LCP)}$

$n \leq 3 \times 10^5，m \leq 10^6$

分析

发现普通的$\texttt{LCP}$可以通过二分$+$哈希求出，我们考虑把这个做法拓展到树上。

维护$\texttt{h[u]}$表示根到$u$路径上的字符串哈希值，$\texttt{revh[u]}$表示$u$到根路径上的哈希值，则$u \sim v$路径上的哈希值可以表现为$\texttt{revh[u, lca]} \times \texttt{base}^{dv} + \texttt{h(lca,v])}$，其中$\texttt{dv}$表示$\texttt{v}$到$\texttt{lca}$的距离；而询问$u$和$v$到$\texttt{lca}$的哈希值可以视为一个序列问题解决。

回到原问题，我们二分$\texttt{LCP}$的长度$\texttt{k}$，并找到$\texttt{(a, b), (c, d)}$路径上第$\texttt{k}$个节点（记为$v_1, v_2$），判断$\texttt{(a,v1)}$与$\texttt{(c,v2)}$链上的哈希值是否相等，并调整二分区间，最后的$l$就是答案

时间复杂度$\mathcal{O}\texttt{((n + m) log n)}$，详细实现参见代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 1e6 + 10;
const int mod = 998244853;

struct edge
{
    int next, to;
};

struct mod_t
{
    static int norm(int x) { return x + (x >> 31 & mod); }
    int x;
    mod_t() {}
    mod_t(int v) : x(v) {}
    mod_t(long long v) : x(v) {}
    mod_t(char v) : x(v) {}
    mod_t operator+(const mod_t &rhs) const { return norm(x + rhs.x - mod); }
    mod_t operator-(const mod_t &rhs) const { return norm(x - rhs.x); }
    mod_t operator*(const mod_t &rhs) const { return (ll)x * rhs.x % mod; }
};

edge e[MaxN << 1];
std::vector<int> up[MaxN], down[MaxN];

char s[MaxN];
int n, m, cnt;
mod_t h[MaxN], revh[MaxN], powm[MaxN], invp[MaxN], base, inv;
int son[MaxN], fa[MaxN][24], f[MaxN][24], Dep[MaxN], pos[MaxN];
int head[MaxN], dep[MaxN], maxd[MaxN], fir[MaxN], lg2[MaxN], top[MaxN];

void add_edge(int u, int v)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

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

int querylca(int u, int v)
{
    int l = fir[u], r = fir[v], k;
    if (l > r) std::swap(l, r);
    k = lg2[r - l + 1];
    return (Dep[f[l][k]] <= Dep[f[r - (1 << k) + 1][k]]) ? pos[f[l][k]] : pos[f[r - (1 << k) + 1][k]];
}

mod_t fast_pow(mod_t a, int b)
{
    mod_t ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a;
        a = a * a, b >>= 1;
    }
    return ret;
}

void init()
{
    srand(time(NULL));
    powm[0] = invp[0] = 1, base = (rand() % 2000) + 1001;
    inv = fast_pow(base, mod - 2);
    for (int i = 1; i <= n; i++)
    {
        powm[i] = (powm[i - 1] * 1ll * base);
        invp[i] = (invp[i - 1] * 1ll * inv);
    }
}

void prework()
{
    lg2[0] = -1;
    for (int i = 1; i <= cnt; i++)
        lg2[i] = lg2[i >> 1] + 1, f[i][0] = i;
    for (int j = 1; (1 << j) <= cnt; j++)
    {
        for (int i = 1; i <= cnt - (1 << j) + 1; i++)
            f[i][j] = (Dep[f[i][j - 1]] <= Dep[f[i + (1 << (j - 1))][j - 1]]) ? f[i][j - 1] : f[i + (1 << (j - 1))][j - 1];
    }
}

inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch - 48), ch = getchar();
    return x;
}

void dfs(int u, int fa)
{
    Dep[++cnt] = maxd[u] = dep[u] = dep[fa] + 1, ::fa[u][0] = fa;
    pos[cnt] = u, h[u] = h[fa] * 1ll * base + s[u];
    fir[u] = cnt, revh[u] = revh[fa] + powm[dep[fa]] * s[u];
    for (int i = 1; i <= 20; i++)
        ::fa[u][i] = ::fa[::fa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa) continue;
        dfs(v, u), pos[++cnt] = u, Dep[cnt] = dep[u];
        if (maxd[v] > maxd[u])
            maxd[u] = maxd[v], son[u] = v;
    }
}

void dfs1(int u, int top)
{
    ::top[u] = top;
    if (u == top)
    {
        int x = u;
        for (int i = 0; i <= maxd[u] - dep[u]; i++)
            up[u].push_back(x), x = fa[x][0];
        x = u;
        for (int i = 0; i <= maxd[u] - dep[u]; i++)
            down[u].push_back(x), x = son[x];
    }
    if (son[u]) dfs1(son[u], top);
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v != son[u] && v != fa[u][0]) dfs1(v, v);
    }
}

int qhash(int u, int v, int lca, int flca)
{
    int dv = dep[v] - dep[lca];
    mod_t h1 = (revh[u] - revh[flca] + mod) * invp[dep[flca]], h2, H;
    h2 = (h[v] - h[lca] * powm[dv]), H = h1 * powm[dv] + h2;
    return H.x;
}

int get(int u, int v, int k)
{
    int lca = querylca(u, v), d = dep[u] + dep[v] - 2 * dep[lca] + 1;
    return (k <= dep[u] - dep[lca]) ? 1 : 0;
}

int path(int u, int v, int k)
{
    int lca = querylca(u, v), d = dep[u] + dep[v] - 2 * dep[lca] + 1;
    if (k <= dep[u] - dep[lca])
        return querykth(u, k - 1);
    else
        return querykth(v, d - k);
}

int query(int a, int b, int c, int d)
{
    if (s[a] != s[c]) return 0;
    int lca1 = querylca(a, b), flca1 = fa[lca1][0], d1 = dep[a] + dep[b] - 2 * dep[lca1] + 1;
    int lca2 = querylca(c, d), flca2 = fa[lca2][0], d2 = dep[c] + dep[d] - 2 * dep[lca2] + 1;
    int l = 1, r = std::min(d1, d2);
    // printf("debug: a = %d, b = %d, c = %d, d = %d, lca(a, b) = %d, lca(c, d) = %d\n", a, b, c, d, lca1, lca2);
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        int x1 = get(a, b, mid), x2 = get(c, d, mid);
        int v1 = path(a, b, mid), v2 = path(c, d, mid);
        // printf("Debug: l = %d, r = %d, mid = %d, v1 = %d, v2 = %d\n", l, r, mid, v1, v2);
        if (qhash(a, v1, (x1 ? v1 : lca1), (x1 ? fa[v1][0] : flca1)) == qhash(c, v2, (x2 ? v2 : lca2), (x2 ? fa[v2][0] : flca2)))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    scanf("%d\n%s", &n, s + 1), init();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        add_edge(u, v), add_edge(v, u);
    }
    m = read(), cnt = 0, dfs(1, 0), dfs1(1, 1), prework();
    for (int i = 1; i <= m; i++)
    {
        int a = read(), b = read(), c = read(), d = read();
        printf("%d\n", query(a, b, c, d));
    }
    return 0;
}
hash, 数据结构, 集训队作业
AGC035D Add and Remove
AGC022E Median Replace
关注我

分类

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×