2019年icpc徐州站L、Loli, Yen-Jen, and a cool problem

传送门
广义SAM模版题 记录一下每个点的父亲节点，每个点对应的状态节点，然后跑广义SAM，统计下数量，跳一下fail边就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 150;
const int kind = 26;
typedef long long ll;
int tot1 = 1, las = 1;
int ch[maxn * 2][kind],len[maxn * 2], fa[maxn * 2];
int cnt[maxn * 2],vis[maxn],d[maxn];
inline int newn(int x) { len[++tot1] = x; return tot1; }
inline int newnq(int p, int w) {
	int nq = newn(len[p] + 1);
	int q = ch[p][w];
	for (int i = 0; i < kind; i++)ch[nq][i] = ch[q][i];
	fa[nq] = fa[q];
	fa[q] = nq;
	while (p&&ch[p][w] == q)ch[p][w] = nq, p = fa[p];
	return nq;
}
void sam_ins(int c) {
	int p = las;
	if (ch[p][c]) {
		int q = ch[p][c];
		if (len[q] == len[p] + 1)las = q;
		else las = newnq(p, c);
		return;
	}
	int np = newn(len[las] + 1); las = tot1;
	while (p && !ch[p][c])ch[p][c] = np, p = fa[p];
	if (!p)fa[np] = 1;
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) fa[np] = q;
		else {
			fa[np] = newnq(p, c);
		}
	}
}
int dd[maxn * 2],who[maxn * 2];
void updatecount() {
	for (int i = 1; i <= tot1; i++)dd[len[i]]++;
	for (int i = 1; i <= tot1; i++)dd[i] += dd[i - 1];
	for (int i = 1; i <= tot1; i++)who[dd[len[i]]--] = i;
	for (int i = tot1; i >= 2; i--)cnt[fa[who[i]]] += cnt[who[i]];
}
int calc(int s,int l) {while (len[fa[s]]>=l){s = fa[s];}return cnt[s];}
char s[maxn];
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	scanf("%s", s);
	for (int i = 2; i <= n; i++)scanf("%d", &vis[i]);
	sam_ins(s[0] - 'A');
	d[1] = las;
	cnt[las]++;
	vis[1] = 1;
	for (int i = 2; i <=n; i++) {
		las = d[vis[i]];
		sam_ins(s[i-1] - 'A');
		cnt[las]++;
		d[i] = las;
	}
	updatecount();
	for (int i = 0; i < q; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", calc(d[a], b));
	}
}