一道串题. 栽在了树链剖分上.

Description

有一棵树, 每个节点有一个串, 每次询问一条路径和几个串, 问路径上最长的这个串的子串有多长.

Solution

所有节点建AC自动机, 在一个串的结尾处打上一个Tag.

然后把询问离线, 沿着AC自动机跑, 沿途打询问Tag.

沿fail树DFS一遍AC自动机, 到一个节点时在线段树上更新一下, 向下DFS时这个点始终可以作为子串贡献. 离开这个点时撤回即可. 在每个节点的询问更新一下答案, 上面沿途经过的线段树更新都是询问串的子串, 所以可以树剖辅助查询.

(于是我就多组数据没有清空重儿子

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 1e+5 + 5;

struct edge {
  int to, nxt;
  edge(int to_ = 0, int n_ = 0):to(to_), nxt(n_){}
}e[maxn << 1];
struct node {
  int len, id;
  node(int l = 0, int i_ = 0):len(l), id(i_){}
};
struct que {
  int x, y, id;
  que(int x_ = 0, int y_ = 0, int i_ = 0):x(x_), y(y_), id(i_){}
};
int n, lnk[maxn], ptr, F[maxn], dfn[maxn], dep[maxn];
int top[maxn], mxson[maxn], siz[maxn], cnt, ans[maxn];
int mx[maxn << 2];
char line[maxn];

inline void add(int bgn, int end) {
  e[++ptr] = edge(end, lnk[bgn]);
  lnk[bgn] = ptr;
}
void dfs(int x) {
  int fa = F[x];
  dep[x] = dep[fa] + 1;
  siz[x] = 1;
  mxson[x] = 0;
  //F[x] = fa;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa) continue;
    dfs(y);
    siz[x] += siz[y];
    if (siz[y] > siz[mxson[x]]) mxson[x] = y;
  }
}
void dfs2(int x, int init) {
  dfn[x] = ++cnt;
  top[x] = init;
  if (!mxson[x]) return;
  dfs2(mxson[x], init);
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == mxson[x] || y == F[x]) continue;
    dfs2(y, y);
  }
}
void update(int cur, int l, int r, int p, int v) {
  if (l == r) {
    mx[cur] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) update(cur << 1, l, mid, p, v);
  else update(cur << 1|1, mid + 1, r, p, v);
  mx[cur] = max(mx[cur << 1], mx[cur << 1|1]);
}
int query(int cur, int l, int r, int L, int R) {
  if (L <= l && r <= R) return mx[cur];
  int mid = (l + r) >> 1, ret = 0;
  if (L <= mid) ret = query(cur << 1, l, mid, L, R);
  if (R > mid) ret = max(ret, query(cur << 1|1, mid + 1, r, L, R));
  return ret;
}
inline int queryt(int x, int y) {
  int ret = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    ret = max(ret, query(1, 1, n, dfn[top[x]], dfn[x]));
    x = F[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  ret = max(ret, query(1, 1, n, dfn[x], dfn[y]));
  return ret;
}

struct ACAutomation {
  int f[maxn], tr[maxn][26], tot;//, lst[maxn];
  vector<node> t[maxn]; 
  vector<que> q[maxn];
  vector<int> v[maxn];
  void clear() {
    //tot = 0;
    memset(f, 0, sizeof f);
    // memset(lst, 0, sizeof lst);
    //memset(val, 0, sizeof val);
    for (int i = 0; i <= tot; ++i) {
      t[i].clear();
      q[i].clear();
      v[i].clear();
      memset(tr[i], 0, sizeof tr[i]);
    }
    tot = 0;
  }
  void Insert(char *s, int id) {
    int l = strlen(s), now = 0;
    for (int i = 0; i < l; ++i) {
      int ch = s[i] - 'a';
      if (!tr[now][ch]) tr[now][ch] = ++tot;
      now = tr[now][ch];
    }
    t[now].push_back(node(l, id));
  }
  void build() {
    f[0] = 0;
    queue<int> q;
    for (int i = 0; i < 26; ++i) {
      if (tr[0][i]) {
        q.push(tr[0][i]);
        f[tr[0][i]] = 0;
        v[0].push_back(tr[0][i]);
      }
    }
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i = 0; i < 26; ++i) {
        if (!tr[u][i]) tr[u][i] = tr[f[u]][i];
        else {
          f[tr[u][i]] = tr[f[u]][i];
          q.push(tr[u][i]);
          v[tr[f[u]][i]].push_back(tr[u][i]);
        }
      }
    }
  }
  void iquery(int x, int y, char *s, int id) {
    int now = 0, l = strlen(s);
    for (int i = 0; i < l; ++i) {
      int ch = s[i] - 'a';
      now = tr[now][ch];
      q[now].push_back(que(x, y, id));
    }
  }
  void solve(int now) {
    // printf("vis %d\n", now);
    for (int i = 0; i < (int)t[now].size(); ++i) {
      update(1, 1, n, dfn[t[now][i].id], t[now][i].len);
    }
    for (int i = 0; i < (int)q[now].size(); ++i) {
      int idx = q[now][i].id;
      // printf("query %d\n", idx);
      ans[idx] = max(ans[idx], queryt(q[now][i].x, q[now][i].y));
    }
    for (int i = 0; i < (int)v[now].size(); ++i)
      solve(v[now][i]);
    for (int i = 0; i < (int)t[now].size(); ++i)
      update(1, 1, n, dfn[t[now][i].id], 0);
  }
}AC;

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    memset(lnk, 0, sizeof lnk);
    ptr = 0; cnt = 0;
    AC.clear();
    for (int i = 1; i <= n; ++i) {
      scanf("%s", line + 1);
      AC.Insert(line + 1, i);
    }
    AC.build();
    int u, v;
    for (int i = 2; i <= n; ++i) {
      scanf("%d", &F[i]);
      add(F[i], i); add(i, F[i]);
    }
    dfs(1);
    dfs2(1, 1);
    int m; scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d%s", &u, &v, line + 1);
      AC.iquery(u, v, line + 1, i);
      ans[i] = 0;
    }
    AC.solve(0);
    for (int i = 1; i <= m; ++i) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}