Clarke and room
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 11 Accepted Submission(s): 3
Problem Description Clarke is a patient with multiple personality disorder. One day, Clarke split into n guys, the i th Clarke named namei .
They live in n rooms connected by n−1 roads. There is only one path between any two rooms. Now, their landlord is to check the name with a long list. The landlord will check m times, at i th time, he wants to know the maximum length of the names which appear on the list si on the path between xi and yi rooms(including xi and yi ).
Input The first line contains an integer T(1≤T≤10) , the number of test cases.
For each test case:
The first line contains an integer n(1≤n≤100000) .
Then n lines follow, the i th line contains a string namei .
Then n−1 lines follow, the i th line contains an integer fi+1(1≤fi+1≤i) , denoting there is an edge between i+1 and fi+1 .
Then m lines follow, the i th line contains two integers xi,yi(1≤xi,yi≤n) and a string si .
Every string is composed by lower letter.
1≤|namei|,|si|,∑ni=1|namei|,∑mi=1|si|≤100000
Output For each test case, print m lines with the answers.
Sample Input
1
4
a
ab
abc
d
1
2
1
3
1 1 abc
1 1 d
1 3 abc
Sample Output
1
0
3
Hint:
Ask 1: $a$ appears in $abc$, so the answer is $1$.
Ask 2: There is no one appears in $d$, so the answer is $0$.
Ask 3: $a$, $ab$ and $abc$ appear in $abc$, so the answer is $3$.
題意：給一棵n個點的樹，每個節點有一個串，然後有m個查詢x y s，查詢點x走到點y路徑上（包含x，y）的串是s的子串的最長的長度是多少
題解：這題我用的是離線的方法，首先熟練剖分作查詢，然後标記好線段樹的每個點被哪些查詢通路，最後單獨對每個存在查詢的線段樹結點建立一棵自動機，把這個線段樹結點包含的區間的串全部插入自動機，然後對逐一對通路過這個區間的串作一次查詢更新對應查詢。複雜度是（name + s）* logn * logn級别的
代碼如下，函數名字已經很清楚說明了函數功能
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int N = 26;
const int maxn = 100008;
int n, p[maxn], fp[maxn];
inline void mymax(int &x, int y){
if(y > x) x = y;
}
struct tire{
int nxt[N + 2], fail, is, len;
void init(){
memset(nxt, 0, sizeof(nxt));
fail = is = len = 0;
}
};
struct act{
tire t[maxn];
int root = 0, all;
void init(){
t[all = 0].init();
}
void insert(string s){
int now = 0;
for(int i = 0; i < (int)s.length(); i++){
int cc = s[i] - 'a';
if(!t[now].nxt[cc]){
t[now].nxt[cc] = ++all;
t[all].init();
}
now = t[now].nxt[cc];
}
t[now].is = 1;
t[now].len = s.length();
}
void build(){
int now = 0;
queue<int> q;
for(int i = 0; i < N; i++){
if(!t[now].nxt[i]) continue;
else{
t[t[now].nxt[i]].fail = 0;
q.push(t[now].nxt[i]);
}
}
while(!q.empty()){
now = q.front();
q.pop();
for(int i = 0; i < N; i++){
if(!t[now].nxt[i]){
t[now].nxt[i] = t[t[now].fail].nxt[i];
}
else{
t[t[now].nxt[i]].fail = t[t[now].fail].nxt[i];
mymax(t[t[now].nxt[i]].len, t[t[t[now].nxt[i]].fail].len);
q.push(t[now].nxt[i]);
}
}
}
}
int run(string s){
int res = 0, now = 0;
for(int i = 0; i < (int)s.length(); i++){
int cc = s[i] - 'a';
now = t[now].nxt[cc];
mymax(res, t[now].len);
}
return res;
}
}ac;
string s[maxn], ans[maxn];
int res[maxn];
struct segtree{
vector<int> v[maxn << 2];
void init(int pos, int l, int r){
v[pos].clear();
if(l == r) return ;
int mid = (l + r) >> 1;
init(pos << 1, l, mid);
init(pos << 1 | 1, mid + 1, r);
}
void query(int pos, int l, int r, int tl, int tr, int vv){
if(tl <= l && r <= tr){
v[pos].push_back(vv);
return ;
}
int mid = (l + r) >> 1;
if(tr <= mid){
query(pos << 1, l, mid, tl, tr, vv);
}
else if(tl > mid){
query(pos << 1 | 1, mid + 1, r, tl, tr, vv);
}
else{
query(pos << 1, l, mid, tl, mid, vv);
query(pos << 1 | 1, mid + 1, r, mid + 1, tr, vv);
}
}
void getans(int pos, int l, int r){
if(v[pos].size()){
//printf("pos %d %d %d\n", pos, l, r);
ac.init();
for(int i = l; i <= r; i++){
ac.insert(s[fp[i]]);
}
ac.build();
for(int i = 0; i < (int)v[pos].size(); i++){
mymax(res[v[pos][i]], ac.run(ans[v[pos][i]]));
}
}
if(l == r) return ;
int mid = (l + r) >> 1;
getans(pos << 1, l, mid);
getans(pos << 1 | 1, mid + 1, r);
}
}st;
struct edge{
int to, nxt;
};
struct slpf{
edge e[maxn << 2];
int head[maxn], top[maxn], fa[maxn];
int deep[maxn], num[maxn];
int son[maxn], tot, pos, root;
void init(){
tot = 0;
memset(head, -1, sizeof(head));
pos = 1;
memset(son, -1, sizeof(son));
}
void addedge(int u, int v){
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot++;
}
void dfs1(int u, int pre, int d){
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for(int i = head[u]; i != -1; i = e[i].nxt){
int v = e[i].to;
if(v != pre){
dfs1(v, u, d + 1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}
void getpos(int u, int sp){
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if(son[u] == -1) return ;
getpos(son[u], sp);
for(int i = head[u]; i != -1; i = e[i].nxt){
int v = e[i].to;
if(v != son[u] && v != fa[u])
getpos(v, v);
}
}
void build(){
dfs1(1, 0, 0);
getpos(1, 1);
}
void query(int u, int v, int vv){
int f1 = top[u], f2 = top[v];
while(f1 != f2){
if(deep[f1] < deep[f2]){
swap(f1, f2);
swap(u, v);
}
st.query(1, 1, n, p[f1], p[u], vv);
//printf("query %d %d\n", p[f1], p[u]);
u = fa[f1];
f1 = top[u];
}
if(deep[u] > deep[v]) swap(u, v);
st.query(1, 1, n, p[u], p[v], vv);
}
}spt;
int main(){
int _, x, y, m;
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0);
cin >> _;
while(_--){
cin >> n;
st.init(1, 1, n);
spt.init();
for(int i = 1; i <= n; i++){
cin >> s[i];
}
for(int i = 1; i < n; i++){
cin >> x;
spt.addedge(i + 1, x);
spt.addedge(x, i + 1);
}
spt.build();
cin >> m;
for(int i = 1; i <= m; i++){
cin >> x >> y >> ans[i];
spt.query(x, y, i);
}
memset(res, 0, sizeof(res));
st.getans(1, 1, n);
for(int i = 1; i <= m; i++){
cout << res[i] << endl;
}
}
return 0;
}
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)