给定一棵 n 个点的树，树上每个节点代表一个小写字母，询问一个字符串 S 是否在树上出现过？ 字符串 S 出现过即表示存在两个点 u,v，u 到 v 的最短路径上依次连接所有点上的字母恰好是 S
N ≤ 10^4
直接寻找即可，注意特殊情况，加一个小优化优化非常多。
1 #include<stdio.h> 2 #include<iostream> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<string> 7 #include<string.h> 8 #include<set> 9 #include<map> 10 #include<vector> 11 #include<time.h> 12 #define il inline 13 #define re register 14 using namespace std; 15 const int N=20001; 16 struct edge{int next,to; 17 } e[N]; 18 int T,n,g[N][26],M,m,d[N],x[N],y[N],exist[101]; 19 bool flag; 20 char p[N],q[N]; 21 il void addedge(re int x,re int y){ 22 e[++M]=(edge){g[x][p[y]-'a'],y};g[x][p[y]-'a']=M; 23 } 24 il bool dfs(re int h,re int fa,re int d){ 25 //printf("%d %d %d ",h,fa,d); 26 if(d==m){ 27 return true; 28 } 29 for(re int i=g[h][q[d+1]-'a'],k;i;i=e[i].next){ 30 k=e[i].to; 31 if(k==fa) continue; 32 if(dfs(k,h,d+1)) return true; 33 } 34 return false; 35 } 36 il bool dfs1(re int h,re int fa){ 37 for(int j=0;j<26;j++){ 38 for(int i=g[h][j];i;i=e[i].next){ 39 if(e[i].to==fa) continue; 40 d[e[i].to]=d[h]+1; 41 dfs1(e[i].to,h); 42 } 43 } 44 } 45 int main(){ 46 freopen("alphabet.in","r",stdin); 47 freopen("alphabet.out","w",stdout); 48 scanf("%d",&T); 49 for(int it=1;it<=T;it++){ 50 memset(g,false,sizeof(g)); 51 memset(exist,false,sizeof(exist)); 52 scanf("%d",&n);M=0;flag=true; 53 for(int i=1;i<n;i++) 54 scanf("%d%d",&x[i],&y[i]); 55 scanf("%s%s",p+1,q+1);m=strlen(q+1); 56 for(int i=1;i<=n;i++) 57 exist[p[i]-'a']++; 58 for(int i=1;i<=m;i++) 59 if(!exist[q[i]-'a']){ 60 flag=false;break; 61 } 62 if(!flag){ 63 printf("Case #%d: Impossible ",it);continue; 64 } 65 int t1=0,t2=0; 66 for(int i=1;i<=n;i++){ 67 if(p[i]==q[1]) t1++; 68 if(p[i]==q[m]) t2++; 69 } 70 for(int i=1;i<n;i++){ 71 addedge(x[i],y[i]); 72 addedge(y[i],x[i]); 73 } 74 d[1]=1;dfs1(1,0); 75 int sp=1; 76 for(int i=1;i<=n;i++) 77 if(d[i]>d[sp]) sp=i; 78 d[sp]=1;dfs1(sp,0); 79 for(int i=1;i<=n;i++) 80 if(d[i]>d[sp]) sp=i; 81 if(d[sp]<m){ 82 printf("Case #%d: Impossible ",it);continue; 83 } 84 if(t2<t1) reverse(q+1,q+m+1); 85 for(int i=1;i<=n;i++){ 86 if(p[i]==q[1]){ 87 if(dfs(i,0,1)){ 88 printf("Case #%d: Find ",it);flag=false;break; 89 } 90 } 91 } 92 if(flag){ 93 printf("Case #%d: Impossible ",it); 94 } 95 // cout<<clock()<<endl; 96 } 97 return 0; 98 }