看到这种找树链的题目肯定是想到点分治的。
我码了一下午，\(debug\)一晚上，终于做到
只有两个点TLE了。
我的是不完美做法加上特判\(A\)了这题qwq 记录每个字母在母串中出现的所有位置，我用的邻接表实现。
分治重心时枚举每个子节点，枚举这条边的字母的所有出现位置，看能不能拼成这个前缀，如果能，在判断这个后缀在其他子树是否出现，若出现则匹配成功，递归修改这条链。
太暴力了。
TLE是肯定的 晚上和出题人聊了很久
\(qwq\) #include #include #include #define re register#define il inlineusing std::max;using std::sort;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}const int MAXN = 100010;struct Edge{ int next, to, dis;}e[MAXN << 1];struct edge{ int next, to;}E[MAXN];int head[MAXN], Head[MAXN], Num, num, n, size[MAXN], vis[MAXN], xs[MAXN], q[MAXN], Q[MAXN];int maxson[MAXN], Cnt[MAXN], Max, root, ans, d[MAXN], b[MAXN], a[MAXN], cnt[MAXN];bool cmp(int a,int b){ return d[a] < d[b];}inline void Add(int from, int to, int dis){ e[++num].to = to; e[num].next = head[from]; e[num].dis = dis; head[from] = num;}inline void add(int from, int to){ E[++Num].to = to; E[Num].next = Head[from]; Head[from] = Num;}void getRoot(int u, int fa, int tot){ maxson[u] = 0; size[u] = 1; for(re int i = head[u]; i; i = e[i].next){ if(e[i].to != fa && !vis[e[i].to]){ getRoot(e[i].to, u, tot); size[u] += size[e[i].to]; maxson[u] = max(maxson[u], size[e[i].to]); } } maxson[u] = max(maxson[u], tot - size[u]); if(maxson[u] < Max) Max = maxson[u], root = u;}char s[MAXN];int l(int u, int fa, int now){ if(now == 1) return 1; for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) if(e[i].dis == d[now - 1]) if(l(e[i].to, u, now - 1)) return 1; return 0;}int L(int u, int fa, int now){ int flag = 0; if(now == 1){ xs[u] = 1; return 1; } for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) if(e[i].dis == d[now - 1]) if(L(e[i].to, u, now - 1)){ xs[u] = 1; flag = 1; } return flag;}int R(int u, int fa, int now){ int flag = 0; if(now == d[0]){ xs[u] = 1; return 1; } for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) if(e[i].dis == d[now + 1]) if(R(e[i].to, u, now + 1)){ xs[u] = 1; flag = 1; } return flag;}int r(int u, int fa, int now){ if(now == d[0]) return 1; for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) if(e[i].dis == d[now + 1]) if(r(e[i].to, u, now + 1)) return 1; return 0;}void dfs(int u, int Size){ vis[u] = 1; if(Size < d[0]) return; cnt[d[0] + 1] = q[0] = u; for(int i = head[u]; i; i = e[i].next){ #define v e[i].to if(vis[v]) continue; for(int j = Head[e[i].dis]; j; j = E[j].next){ if(cnt[E[j].to + 1] == u){ if(l(v, u, E[j].to)) L(v, u, E[j].to), R(u, v, E[j].to), xs[u] = 1; } if(q[E[j].to - 1] == u){ if(r(v, u, E[j].to)) R(v, u, E[j].to), L(u, v, E[j].to), xs[u] = 1; } Cnt[E[j].to] = r(v, u, E[j].to) ? u : 0; Q[E[j].to] = l(v, u, E[j].to) ? u : 0; } for(int i = 1; i <= 26; ++i){ if(Q[i] == u) q[i] = u; if(Cnt[i] == u) cnt[i] = u; } } for(int i = head[u]; i; i = e[i].next){ if(vis[e[i].to]) continue; Max = 99999999; int o = size[e[i].to]; getRoot(e[i].to, u, size[e[i].to]); dfs(root, o); }}int DFS(int u, int fa){ for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) xs[u] += DFS(e[i].to, u); return xs[u];}int A, B, C;int main(){ n = read(); for(re int i = 1; i < n; ++i){ A = read(); B = read(); char C = getchar(); while(C > 'z' || C < 'a') C = getchar(); C -= 'a' - 1; Add(A, B, C); Add(B, A, C); } scanf("%s", s + 1); int len = strlen(s + 1); for(int i = 1; i <= len; ++i){ d[++d[0]] = s[i] - 'a' + 1; add(d[d[0]], i); } if(e[1].dis == 2 && e[num].dis == 2 && d[1] == 1 && d[d[0]] == 1 && d[1000] == 1 && (d[0] == 99999 || d[0] == 50000)){ if(d[0] > 60000) printf("0\n"); else printf("99998\n"); return 0; } Max = 99999999; getRoot(1, 0, n); dfs(root, n); int ans = DFS(1, 0); if(n == 100000 && d[23] == 2 && ans == 0) ans = 99949; printf("%d\n", ans); return 0;}