我在昨天晚上写这道题的时候，天真地认为 $fail_i \le i$，然后直接迭代更新的 $\textrm{siz}$ 数组：

void refresh() {
	for(int i = cntNode; i >= 1; --i) {
		siz[fail[i]] += siz[i];
	}
}

然后他挂了 /kk

今天早上我看了 ouuan 的题解，老老实实建出了 fail 树之后 dfs 更新的 siz 数组：

void dfs(int x, int p) {
	for(int i = first[x]; ~i; i = e[i]._next) {
		int y = e[i].to;
		if(y == p)
			continue;
		dfs(y, x);
		siz[x] += siz[y];
	}
}
void refresh() {
	for(int i = 1; i <= cntNode; ++i)
		add(i, fail[i]), add(fail[i], i);
	dfs(0, 0);
}

然后就过了。

我认为是存在 $fail_i > i$ 的问题，然后在第一份代码中 assert(fail[i] <= i); 了一下，然后 44pts（其余 RE）。

请问这是什么情况？AC 自动机上的 fail 指针为什么会指向编号大于自己的节点呢？

是因为建「Trie 图」问题吗？（就是建 trie 的时候，更改了 trie 本身的结构：

void build() {
	std::queue <int> q;
	for(int i = 1; i <= C; ++i)
		if(ch[0][i])
			q.push(ch[0][i]);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 1; i <= C; ++i) {
			int &v = ch[u][i];
			if(v)
				fail[v] = ch[fail[u]][i], q.push(v);
			else
				v = ch[fail[u]][i]; // 这一行
		}
	}
}

如能解决，不胜感激！