记录编号	385988	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.731 s
提交时间	2017-03-23 06:38:31	内存使用	20.91 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 200005;
struct Edge {
	int next, to;
	Edge(int a=0, int b=0) : next(a), to(b) {}
} e[maxn];
int head[maxn], tot;
void Add(int u, int v) {
	e[++tot] = Edge(head[u], v); head[u] = tot;
}
struct AC {
	map<int,int> ch[maxn];
	int p_, h[maxn], fail[maxn];
	int insert(vector<int> s, int n) {
		int x = 0;
		for(int i=0; i<n; ++i) {
			int c = s[i];
			if(!ch[x].count(c)) ch[x][c] = ++p_;
			x = ch[x][c];
		}
		++h[x]; return x;
	}
#define travel(i, v) for(map<int,int>::iterator i=v.begin(); i!=v.end(); ++i)
	void build() {
		static queue<int> q;
		travel(i, ch[0]) q.push(i->second);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			travel(i, ch[x]) {
				int c = i->first, to = i->second;
				q.push(to);
				int t = fail[x];
				while(t && !ch[t].count(c)) t = fail[t];
				fail[to] = t = ch[t].count(c) ? ch[t][c] : 0;
				h[to] = h[to]+h[t];
			}
		}
		for(int i=1; i<=p_; ++i) Add(fail[i], i);
	}
	void find(vector<int> s, int n, vector<int> &f) {
		int x = 0;
		for(int i=0; i<n; ++i) {
			int c = s[i];
			while(x && !ch[x].count(c)) x = fail[x];
			x = ch[x].count(c) ? ch[x][c] : 0;
			f.push_back(x);
		}
	}
} ac;
namespace tree {
	int dfs_cnt, dfn[maxn], post[maxn], top[maxn];
	int fa[maxn], son[maxn], size[maxn], depth[maxn];
	void dfs(int x) {
		size[x] = 1;
		for(int i=head[x]; i; i=e[i].next) {
			int to = e[i].to;
			depth[to] = depth[x]+1;
			fa[to] = x;
			dfs(to);
			size[x] += size[to];
			if(!son[x] || size[son[x]]<size[to]) son[x] = to;
		}
	}
	void build(int x, int tp) {
		dfn[x] = ++dfs_cnt;
		top[x] = tp;
		if(son[x]) build(son[x], tp);
		for(int i=head[x]; i; i=e[i].next) {
			int to = e[i].to;
			if(!dfn[to]) build(to, to);
		}
		post[x] = dfs_cnt;
	}
	int LCA(int x, int y) {
		while(top[x]!=top[y]) {
			if(depth[top[x]]<depth[top[y]]) swap(x, y);
			x = fa[top[x]];
		}
		return depth[x] < depth[y] ? x : y;
	}
}
namespace bit {
	int c[maxn];
	void add(int p, int v) {
		for(; p<=tree::dfs_cnt; p+=p&-p) c[p] += v;
	}
	int query(int p) {
		int ans = 0;
		for(; p; p-=p&-p) ans += c[p];
		return ans;
	}
}
using namespace tree;
using namespace bit;
int N, M, id[maxn], ans[maxn];
vector<int> s1[maxn], s2[maxn], s, p;
bool cmp(const int& x, const int& y) { return dfn[x] < dfn[y]; }
int solve(int i) {
	p.clear();
	ac.find(s1[i], s1[i].size(), p);
	ac.find(s2[i], s2[i].size(), p);
	sort(p.begin(), p.end(), cmp);
	int ans = ac.h[p[0]];
	add(dfn[p[0]], 1);
	for(int i=1; i<(int)p.size(); ++i) {
		int lca = LCA(p[i-1], p[i]);
		ans += ac.h[p[i]]-ac.h[lca];
		add(dfn[p[i]], 1);
		add(dfn[lca], -1);
	}
	return ans;
}
int main() {
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	scanf("%d%d", &N, &M);
	for(int i=1, x, y; i<=N; ++i) {
		scanf("%d", &x);
		for(int j=0; j<x; ++j) 
			scanf("%d", &y), s1[i].push_back(y);
		scanf("%d", &x);
		for(int j=0; j<x; ++j) 
			scanf("%d", &y), s2[i].push_back(y);
	}
	for(int i=1, x, y; i<=M; ++i) {
		scanf("%d", &x);
		s.clear();
		for(int j=0; j<x; ++j) 
			scanf("%d", &y), s.push_back(y);
		id[i] = ac.insert(s, x);
	}
	ac.build();
	tree::dfs(0);
	tree::build(0, 0);
	for(int i=1; i<=N; ++i) ans[i] = solve(i);
	for(int i=1; i<=M; ++i) 
		printf("%d\n", query(post[id[i]])-query(dfn[id[i]]-1));
	for(int i=1; i<=N; ++i) printf("%d ", ans[i]); puts("");
	getchar(), getchar();
	return 0;
}