【BZOJ 4598】【SDOI 2016 Round2 Day1 T3】模式字符串

2016-05-21因为BZOJ上“ 数据文件太过巨大，仅提供前三组数据测试.”所以我考场上写的60分的点分治交上去也A了。

我的这个点分治的时间复杂度是$O(Tnmlogn)$的，听题解时没听懂$O(Tnlogn)$的标算，还有听说标算要用到字符串哈希，然而我并不会，所以先留个坑，贴上自己的60分代码，满分做法等我学会哈希之后再做

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000003;
void read(int &k) {
	k = 0; int fh = 1; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar())
		if (c == '-') fh = -1;
	for(; c >= '0' && c <= '9'; c = getchar())
		k = (k << 1) + (k << 3) + c - '0';
	k = k * fh;
}

struct node {int nxt, to;} E[N << 1];
int n, m, cnt, point[N], root, qu[N], fa[N], t[N], sz[N];
char c[N], mu[N];
bool vis[N], bo[N];

void ins(int x, int y) {E[++cnt].nxt = point[x]; E[cnt].to = y; point[x] = cnt;}
void findrt(int x) {
	int p = 0, u, q = 1; qu[1] = x; fa[x] = 0;
	while (p != q) {
		u = qu[++p]; bo[u] = 1; sz[u] = 1;
		for(int tmp = point[u]; tmp; tmp = E[tmp].nxt)
			if (!vis[E[tmp].to] && E[tmp].to != fa[u])
				qu[++q] = E[tmp].to, fa[E[tmp].to] = u;
	}
	for(int i = q; i >= 1; --i) {
		u = qu[i];
		if (bo[u] && sz[u] * 2 > q) {root = u; return;}
		sz[fa[u]] += sz[u];
		if (sz[u] * 2 > q) bo[fa[u]] = 0;
	}
}
int leftnow, rightnow, leftsum, rightsum, ret;
void BFSleft(int x) {
	int p = 0, u, q = 1, tt; qu[1] = x;
	while (p != q) {
		u = qu[++p];
		for(int tmp = point[u]; tmp; tmp = E[tmp].nxt)
			if (!vis[E[tmp].to] && E[tmp].to != fa[u] && c[E[tmp].to] == mu[tt = ((t[u] - 1 + m) % m)])
				fa[E[tmp].to] = u, t[E[tmp].to] = tt, qu[++q] = E[tmp].to;
	}
	for(int i = 1; i <= q; ++i)
		if (t[qu[i]] == 0) ++leftnow;
}
void BFSright(int x) {
	int p = 0, u, q = 1, tt; qu[1] = x;
	while (p != q) {
		u = qu[++p];
		for(int tmp = point[u]; tmp; tmp = E[tmp].nxt)
			if (!vis[E[tmp].to] && E[tmp].to != fa[u] && c[E[tmp].to] == mu[tt = ((t[u] + 1) % m)])
				fa[E[tmp].to] = u, t[E[tmp].to] = tt, qu[++q] = E[tmp].to;
	}
	for(int i = 1; i <= q; ++i)
		if (t[qu[i]] == (m - 1)) ++rightnow;
}
void work(int x) {
	vis[x] = 1;
	int tt;
	for(int to = 0; to < m; ++to)
		if (c[x] == mu[to]) {
			leftsum = 0; rightsum = 0; if (to == 0) leftsum = 1; if (to == m - 1) rightsum = 1;
			for(int i = point[x]; i; i = E[i].nxt)
				if (!vis[E[i].to]) {
					leftnow = 0;
					if (c[E[i].to] == mu[tt = (to - 1 + m) % m])
						fa[E[i].to] = x, t[E[i].to] = tt, BFSleft(E[i].to);
					rightnow = 0;
					if (c[E[i].to] == mu[tt = (to + 1) % m])
						fa[E[i].to] = x, t[E[i].to] = tt, BFSright(E[i].to);
					ret += leftsum * rightnow;
					ret += rightsum * leftnow;
					leftsum += leftnow; rightsum += rightnow;
					leftnow = 0; rightnow = 0;
				}
		}
	for(int i = point[x]; i; i = E[i].nxt)
		if (!vis[E[i].to]) {findrt(E[i].to); work(root);}
}
int main() {
	freopen("pattern.in", "r", stdin);
	freopen("pattern.out", "w", stdout);
	int T, u, v;
	read(T);
	while (T--) {
		read(n); read(m);
		scanf("%s", c + 1);
		cnt = 0; memset(point, 0, sizeof(point)); memset(vis, 0, sizeof(vis));
		for(int i = 1; i < n; ++i) {read(u); read(v); ins(u, v); ins(v, u);}
		scanf("%s", mu);
		ret = 0;
		findrt(1);
		work(root);
		printf("%d
", ret);
	}
	return 0;
}