Hiten /bx /bx。

唐诗赤石题。

首先显然答案只有 $O(n)$ 种，我们任取一个叶子节点，那么他到他父亲的边一定是合法字符串的开头，所以答案集合一定是他到所有点的路径字符串集合的子集，于是我们枚举这 $n$ 个字符串依次判断是否合法即可。

判断一个字符串是否合法，那么可以找到这个字符串在树上的所有出现位置，然后用树上差分给边加一，最后判断每条边是否都有权值。于是我们对每个点记录以他为起点的所有字符串的结尾位置，这个可以哈希之后套一个 unordered_map 或其他哈希表记录下标，然后用 $O(n^2)$ 个 vector 存路径终点。那么判断一个字符串是否合法就是枚举每个点作为起点，哈希值相同的路径的结尾位置，然后树上差分，最后判断每条边是否合法。树上差分的部分每次 $O(n)$，总复杂度 $O(n^2)$，前面枚举路径的部分由于总路径数 $O(n^2)$，所以总复杂度 $O(n^2)$，然后做完了。注意树上差分中求 LCA 的部分不能带 $\log$，可以暴力跳但是加记忆化。以及一个字符串合法那么它倒过来也合法，所以也要计入答案并去重。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
using namespace std;
const int N = 2e3 + 10;
const ull MOD = 998244853;
const ull P = 131;
int n; vector<pair<int, char> > G[N];
unordered_map<ull, int> idx[N]; int len[N];
vector<int> vec[N][N]; int lca[N][N];
int S;
void DFS1(int u, int f, ull hsh) {
	if (idx[S].find(hsh) == idx[S].end()) idx[S][hsh] = ++ len[S];
	vec[S][idx[S][hsh]].push_back(u);
	for (auto [v, c] : G[u]) if (v != f) DFS1(v, u, (hsh * P + c) % MOD);
}
int depth[N], fa[N];
void DFS2(int u, int f) {
	depth[u] = depth[f] + 1, fa[u] = f; for (auto [v, c] : G[u]) if (v != f) DFS2(v, u);
}
int LCA(int u, int v) {
	if (lca[u][v] != -1) return lca[u][v];
	if (u == v) return lca[u][v] = u;
	if (depth[u] < depth[v]) swap(u, v);
	return lca[u][v] = lca[v][u] = LCA(fa[u], v);
}
int sum[N];
void DFS3(int u, int f) {
	for (auto [v, c] : G[u]) if (v != f) DFS3(v, u), sum[u] += sum[v];
}
bool res[N]; string cur; set<string> Ans;
void DFS4(int u, int f) {
	if (res[u]) {
		Ans.insert(cur); string tmp;
		for (int i = (int)cur.size() - 1; i >= 0; i --) tmp.push_back(cur[i]);
		Ans.insert(tmp);
	}
	for (auto [v, c] : G[u]) if (v != f) {
		cur.push_back(c); DFS4(v, u); cur.pop_back();
	} return ;
}
int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n; char c;
	for (int i = 1, u, v; i < n; i ++) {
		cin >> u >> v >> c; G[u].push_back({v, c}), G[v].push_back({u, c});
	}
	for (int i = 1; i <= n; i ++) S = i, DFS1(i, 0, 0);
	DFS2(1, 0);
	memset(lca, -1, sizeof lca);
	S = 1; while (G[S].size() > 1) ++ S;
	for (auto [hsh, o] : idx[S]) {
		for (int i = 1; i <= n; i ++) sum[i] = 0;
		for (int i = 1; i <= n; i ++) if (idx[i].find(hsh) != idx[i].end()) {
			int t = idx[i][hsh];
			for (int j : vec[i][t]) sum[i] ++, sum[j] ++, sum[LCA(i, j)] -= 2;
		}
		DFS3(1, 0); bool flag = true;
		for (int i = 2; i <= n; i ++) flag &= (sum[i] != 0);
		if (flag) res[vec[S][o][0]] = 1;
	} DFS4(S, 0);
	cout << Ans.size() << "\n";
	for (string s : Ans) cout << s << "\n";
	return 0;
}