常州day1p4

给定一棵 n 个点的树，树上每个节点代表一个小写字母，询问一个字符串 S 是否在树上出现过？ 字符串 S 出现过即表示存在两个点 u,v，u 到 v 的最短路径上依次连接所有点上的字母恰好是 S

N ≤ 10^4

直接寻找即可，注意特殊情况，加一个小优化优化非常多。

 #include<stdio.h>

 #include<iostream>

 #include<stdlib.h>

 #include<math.h>

 #include<algorithm>

 #include<string>

 #include<string.h>

 #include<set>

 #include<map>

 #include<vector>

 #include<time.h>

 #define il inline

 #define re register

 using namespace std;

 const int N=;

 struct edge{int next,to;

 } e[N];

 int T,n,g[N][],M,m,d[N],x[N],y[N],exist[];

 bool flag;

 char p[N],q[N];

 il void addedge(re int x,re int y){

     e[++M]=(edge){g[x][p[y]-'a'],y};g[x][p[y]-'a']=M;

 }

 il bool dfs(re int h,re int fa,re int d){

     //printf("%d %d %d\n",h,fa,d);

     if(d==m){

         return true;

     }

     for(re int i=g[h][q[d+]-'a'],k;i;i=e[i].next){

         k=e[i].to;

         if(k==fa) continue;

         if(dfs(k,h,d+)) return true;

     }

     return false;

 }

 il bool dfs1(re int h,re int fa){

     for(int j=;j<;j++){

         for(int i=g[h][j];i;i=e[i].next){

             if(e[i].to==fa) continue;

             d[e[i].to]=d[h]+;

             dfs1(e[i].to,h);

         }

     }

 }

 int main(){

     freopen("alphabet.in","r",stdin);

     freopen("alphabet.out","w",stdout);

     scanf("%d",&T);

     for(int it=;it<=T;it++){

         memset(g,false,sizeof(g));

         memset(exist,false,sizeof(exist));

         scanf("%d",&n);M=;flag=true;

         for(int i=;i<n;i++)

             scanf("%d%d",&x[i],&y[i]);

         scanf("%s%s",p+,q+);m=strlen(q+);

         for(int i=;i<=n;i++)

             exist[p[i]-'a']++;

         for(int i=;i<=m;i++)

             if(!exist[q[i]-'a']){

                 flag=false;break;

             }

         if(!flag){

             printf("Case #%d: Impossible\n",it);continue;

         }

         int t1=,t2=;

         for(int i=;i<=n;i++){

             if(p[i]==q[]) t1++;

             if(p[i]==q[m]) t2++;

         }

         for(int i=;i<n;i++){

             addedge(x[i],y[i]);

             addedge(y[i],x[i]);

         }

         d[]=;dfs1(,);

         int sp=;

         for(int i=;i<=n;i++)

             if(d[i]>d[sp]) sp=i;

         d[sp]=;dfs1(sp,);

         for(int i=;i<=n;i++)

             if(d[i]>d[sp]) sp=i;

         if(d[sp]<m){

             printf("Case #%d: Impossible\n",it);continue;

         }

         if(t2<t1) reverse(q+,q+m+);

         for(int i=;i<=n;i++){

             if(p[i]==q[]){

                 if(dfs(i,,)){

                     printf("Case #%d: Find\n",it);flag=false;break;

                 }

             }

         }

         if(flag){

             printf("Case #%d: Impossible\n",it);

         }

     //    cout<<clock()<<endl;

     }

     return ;

 }