题目链接：

题意：

给你一颗树，每个节点有一个字符，现在给你一个字符串S，问你是否能在树上找到两个节点u，v，使得u到v的最短路径构成的字符串恰好为S。

题解：

这题可以用树的分治+字符串hash，不过搜索+剪枝写的好一样可以过，而且跑的时间和正解差不多。

搜索的做法就是先随便找一个点当作根，然后预处理一下最大的深度，然后枚举起点，开始向各个方向遍历，如果这个点的最大深度小于未匹配的字符串长度，那么久向父亲方面搜。

1 #include
      
        2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 const int N=1e4+7; 5  6 int t,n,g[N],v[N*2],nxt[N*2],ed,fg,ic,len,dep[N],mxdep[N],vis[N],fa[N]; 7 char str[N],S[N]; 8  9 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}10 inline void up(int &a,int b){
    if(a
       
        len-now)30     {31         for(int i=g[u];i;i=nxt[i])32             if(str[v[i]]==S[now+1]&&!vis[v[i]])33                 vis[v[i]]=1,dfs_find(v[i],now+1),vis[v[i]]=0;34     }35     else if(str[fa[u]]==S[now+1]&&!vis[fa[u]])36                 vis[fa[u]]=1,dfs_find(fa[u],now+1),vis[fa[u]]=0;37 }38 39 int main()40 {41     scanf("%d",&t);42     while(t--)43     {    44         scanf("%d",&n);45         memset(g,0,sizeof(g)),ed=0;46         F(i,1,n-1)47         {48             int x,y;49             scanf("%d%d",&x,&y);50             adg(x,y),adg(y,x);51         }52         scanf("%s%s",str+1,S+1);53         len=strlen(S+1);54         memset(vis,0,sizeof(vis));55         init_dfs(1),fg=0;56         F(i,1,n)if(str[i]==S[1])57         {58             memset(vis,0,sizeof(vis));59             vis[i]=1,dfs_find(i,1);60         }61         printf("Case #%d: %s\n",++ic,fg?"Find":"Impossible");62     }63     return 0;64 }