C++(clang++11) 解法, 执行用时: 893ms, 内存消耗: 212976K, 提交时间: 2020-11-23 19:19:23

#include <bits/stdc++.h>
#define inc(l,i,r) for (int i=l;i<=r;i++)
#define dec(r,i,l) for (int i=r;i>=l;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 400400;

struct state {int nxt[26], pre, len;} st[N*2];
int sz;

inline int extend(int last,int c) {
	int p = last, now = ++sz;
	st[now].len = st[last].len + 1;
	for (;~p && !st[p].nxt[c];p=st[p].pre) st[p].nxt[c] = now;
	if (p == -1) st[now].pre = 0;  else {
		int q = st[p].nxt[c];
		if (st[q].len == st[p].len+1) st[now].pre = q;  else {
			int clone = ++sz;
			st[clone] = st[q];  st[clone].len = st[p].len + 1;
			for (;~p && st[p].nxt[c] == q;p=st[p].pre) st[p].nxt[c] = clone;
			st[now].pre = st[q].pre= clone;
		}
	} return now;
}

int nxt[N][26], chr[N], f[N][20], pos[N];

inline int F(int x,int len) {
	dec(19,i,0) if (len >> i & 1) {
		x = f[x][i];
	}
	return x;
}

int Len;
bool cmp(int x,int y) {
	//printf("Len = %d cmp %d %d = %d\n",Len,x,y,chr[F(pos[x],Len)] < chr[F(pos[y],Len)]);
	return chr[F(pos[x],Len)] < chr[F(pos[y],Len)];
}

inline void build() {
	queue<pii> Q;
	Q.push(mp(0,0));
	while (!Q.empty()) {
		pii u = Q.front();  Q.pop();
		pos[u.se] = u.fi;
		inc(0,i,25) if (nxt[u.fi][i]) {
			int now = nxt[u.fi][i];
			Q.push(mp(now,extend(u.se,i)));
			chr[now] = i;
			f[now][0] = u.fi;
			inc(1,j,19) f[now][j] = f[f[now][j-1]][j-1];
		}
	}
}

int T, n, q, a[N], fa[N];
char s[N];
bool flag[N*2];
vector<int> belong[N*2], G[N*2], result;

int getfa(int x) {return (fa[x] == x) ? x : fa[x] = getfa(fa[x]);}

void dfs0(int u) {
	for (int v : G[u]) dfs0(v);
	if (u && pos[st[u].pre] == 0) {
		flag[st[u].pre] = true;
		pos[st[u].pre] = pos[u];
	}
}

void dfs(int u) {
	if (!flag[u]) {
		vector<int> &tmp = belong[pos[u]];
		for (int x : tmp) result.pb(x);
	}
	for (int v : G[u]) dfs(v);
}

int main() {
	//freopen("_in.txt","r",stdin);
	scanf("%d",&T);
	while (T--) {
		memset(st,0,sizeof(st));
		memset(nxt,0,sizeof(nxt));
		memset(chr,0,sizeof(chr));
		memset(f,0,sizeof(f));
		memset(pos,0,sizeof(pos));
		memset(flag,0,sizeof(flag));
		st[0].pre = -1;
		sz = 0;
		scanf("%d%d",&n,&q);
		
		result.clear();
		inc(0,i,n) {
			fa[i] = i;
			belong[i].clear();
		}
		scanf("%s",s+1);
		a[1] = 0;
		inc(2,i,n) scanf("%d",a+i);
		inc(1,i,n) {
			if (nxt[getfa(a[i])][s[i]-'a'])	{
				fa[i] = getfa(nxt[getfa(a[i])][s[i]-'a']);
			} else {
				nxt[getfa(a[i])][s[i]-'a'] = i;
			}
		}
		inc(1,i,n) belong[getfa(i)].pb(i);
		build();
		
		inc(1,i,sz) G[st[i].pre].pb(i);
		dfs0(0);

		inc(0,i,sz) {
			Len = st[i].len;
			sort(G[i].begin(),G[i].end(),cmp);
			// printf("%d | ",i);
			// for (int x : G[i]) printf("%d ",x);
			// putchar('\n');
		}
		dfs(0);
		// for (int i=0;i<(int)result.size();i++) printf("%d ",result[i]);
		// putchar(10);
		
		while (q--) {
			int k;
			scanf("%d",&k);
			printf("%d\n",result[k-1]);
		}
		inc(0,i,sz) {
			G[i].clear();
		}
	}
}