提供更为清晰易懂的代码。

考虑 DP，设 $f_{u,t}$ 表示 $u$ 及其子树均已被路径完全覆盖，且至少还能从 $u$ 向上继续覆盖长度 $t$ 的最小代价。

对于 $u$ 的每个孩子 $v$，依次计入 $f$，有：

$$f_{u,\max\{j,k - 1\}} = \displaystyle\min_{\substack{0 \le j < \text{dep}_u\\1 \le k < \text{dep}_v}}\{f_{u,j} + f_{v,k}\}$$

注意转移可能会修改当前 DP 值，故应当先转移后整体覆盖 $f$。

对于输出方案，我们观察转移式子，可以记 $g_{u,t,v} = \left(j,k\right)$ 表示最终的转移式为：

$$f_{u,t} = f_{u,j} + f_{v,k}$$

于是我们可以递归处理方案输出，不断将一个转移状态 $\left(u,t\right)$ 通过枚举儿子 $v$ 化为子问题 $\left(u,g_{u,t,v,0}\right),\left(v,g_{u,t,v,1}\right)$。最后根据 $t$ 的取值输出方案。同时应当注意将枚举儿子的顺序反过来。

使用树上进制哈希初始化，设进制为 $B$，则有：

$$H_u = BH_{\text{fa}_u} + w\left(u,\text{fa}_u\right)$$

若要取出一段哈希值，设 $v$ 是 $u$ 的 $k$ 级祖先，有：

$$H_{u\leftrightarrow v} = H_v - H_uB^{k}$$

这样我们就可以用 $W_H,I_H$ 分别表示哈希值为 $H$ 的路径的最小代价及其编号，以辅助转移。

于是可以初始化：

$$\begin{cases} f_{u,0} &= 0\\ f_{u,t} &= W_H \end{cases}$$

其中 $H$ 是 $u$ 至其 $t$ 级祖先的路径哈希值。

这样总时间复杂度为 $\mathcal{O}\left(n^3\right)$，本题的实现笔者采用了 map 作为哈希表，跑起来也很快。

::::success[代码]

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr int N = 5e2 + 5, M = 1e5 + 5;
constexpr ull P = 212370440131237957;

int n, m, t;
int fa[N][N], dep[N];
ll I;
ll tmp[N], f[N][N];
vector<int> T[N];
ull pw[N] = {1}, hsh[N];
map<ull, ll> w, id;
map<ll, pair<ll, ll>> g[N][N];
struct PATH {
	int l, r, id;
	PATH() {}
	PATH(int a, int b, int c) : l(a), r(b), id(c) {}
};
vector<PATH> ans;
inline ull calc(int u, int v, int len) {return hsh[u] - hsh[v] * pw[len];}
inline void DP(int u) {
	f[u][0] = 0;
	for(int i = 1, now = u ; i <= dep[u] ; i ++) {
		now = fa[now][1];
		if(w[calc(u, now, i)]) {f[u][i] = w[calc(u, now, i)];}
	}
	for(auto v : T[u]) {
		DP(v);
		memset(tmp, 0x3f, sizeof tmp);
		for(int i = 0 ; i <= n ; i ++) {
			if(f[u][i] < I) {
				for(int j = 1 ; j <= n ; j ++) {
					if(f[v][j] < I && tmp[max(i, j - 1)] > f[u][i] + f[v][j]) {
						tmp[max(i, j - 1)] = f[u][i] + f[v][j];
						g[u][max(i, j - 1)][v] = make_pair(i, j);
					}
 				}
			}
		}
		memcpy(f[u], tmp, sizeof tmp);
	}
	return;
}
inline void print(int u, int t) {
	reverse(begin(T[u]), end(T[u]));
	for(auto v : T[u]) {
		print(v, g[u][t][v].second);
		t = g[u][t][v].first;
	}
	if(t) {
		ans.push_back(PATH(fa[u][t], u, id[calc(u, fa[u][t], t)]));
	}
	return;
}
inline void solve() {
	cin>>n>>m>>t;
	for(int i = 2 ; i <= n ; i ++) {
		char c;
		cin>>fa[i][1]>>c;
		dep[i] = dep[fa[i][1]] + 1;
		hsh[i] = hsh[fa[i][1]] * P + ull(c - 'a' + 1);
		T[fa[i][1]].push_back(i);
	}
	for(int i = 1 ; i <= n ; i ++) {
		for(int j = 2 ; j <= n ; j ++) {
			fa[i][j] = fa[fa[i][j - 1]][1];
		}
	}
	for(int i = 1 ; i <= n ; i ++) {pw[i] = pw[i - 1] * P;}
	for(int i = 1 ; i <= m ; i ++) {
		ll ww;
		ull H = 0;
		string s;
		cin>>ww>>s;
		for(auto j : s) {H = H * P + (j - 'a' + 1);}
		if(!w[H] || w[H] > ww) {w[H] = ww, id[H] = i;}
	}
	memset(f, 0x3f, sizeof f);
	I = f[0][0];
	DP(1);
	cout<<(f[1][0] == I ? -1 : f[1][0])<<endl;
	print(1, 0);
	if(t && f[1][0] < I) {
		cout<<ans.size()<<endl;
		for(auto i : ans) {cout<<i.l<<" "<<i.r<<" "<<i.id<<endl;}
	}
	return;
}

signed main() {
	ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
	int TC = 1;
#ifdef MSOD
	cin>>TC;
#endif
	while(TC --) {solve();}
	return 0;
}

::::