100%对

#include <stdio.h>
#define md 998244353
struct SJd {
int l,r,c;
};
int getsum(int x, int y) {
return 1ll * (x - y + 1 + x) * y / 2 % md;
}
struct String {
SJd sz[100010];
int ne[100010],cd;
String() {
cd = 0;
sz[0].l = sz[0].r = 0;
ne[0] = -1;
}
int getne(int x) {
if (ne[x] == -1 || sz[ne[x]].r * 2 <= sz[x].r + 1) return ne[x];
else return ne[x] % (x - ne[x]);
}
int insert(int x, int c) {
cd += 1;
sz[cd].l = sz[cd - 1].r + 1;
sz[cd].r = sz[cd].l + x - 1;
sz[cd].c = c;
ne[cd] = 0;
if (cd == 1) return getsum(x - 1, x);
int p = getne(cd - 1),ma = 0,rt = 0,
tp = ne[cd - 1];
while (p != -1) {
int t = (sz[tp + 1].c == c ? sz[tp + 1].r - sz[tp + 1].l + 1 : 0);
bool b = false;
if (t > x) {
t = x;
b = true;
}
if (t > ma) {
rt = (rt + getsum(sz[tp].r + t, t - ma)) % md;
ma = t;
}
if (t == x && !b) {
ne[cd] = tp + 1;
break;
}
p = getne(p);
tp = ne[tp];
}
if (ma < x && sz[1].c == c) {
rt = (rt + 1ll * (x - ma) * (sz[1].r - sz[1].l + 1)) % md;
ne[cd] = 1;
}
return rt;
}
};
String str;
int tm[100010],ans[100010];
int fr[100010],ne[100010],v[100010],bs = 0;
int lx[100010],x[100010],c[100010];
void addb(int a, int b) {
v[bs] = b;
ne[bs] = fr[a];
fr[a] = bs++;
}
void dfs(int u, int he) {
int oldcd = str.cd;
if (u != 0) he = (he + str.insert(x[u], c[u])) % md;
ans[u] = he;
for (int i = fr[u]; i != -1; i = ne[i]) dfs(v[i], he);
str.cd = oldcd;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i <= n; i++) fr[i] = -1;
for (int i = 1; i <= n; i++) {
int lx;
scanf("%d", &lx);
if (lx == 1) {
char ch[2];
scanf("%d%s", &x[i], ch);
c[i] = ch[0] - 'a';
addb(tm[i - 1], i);
tm[i] = i;
} else {
int a;
scanf("%d", &a);
tm[i] = tm[a];
}
}
dfs(0, 0);
for (int i = 1; i <= n; i++) {
if (lx[i] == 1) printf("%d\n", ans[i]);
else printf("%d\n", ans[tm[i]]);
}
return 0;
}