hdu 5469 Antonidas(树的分治+字符串hashOR搜索+剪枝)

题意：

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

题解：

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

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

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int N=1e4+;

 int t,n,g[N],v[N*],nxt[N*],ed,fg,ic,len,dep[N],mxdep[N],vis[N],fa[N];

 char str[N],S[N];

 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}

 inline void up(int &a,int b){if(a<b)a=b;}

 void init_dfs(int u)

 {

     int ma=-N;

     mxdep[u]=,vis[u]=;

     for(int x=g[u];x;x=nxt[x])if(!vis[v[x]])

     {

         init_dfs(v[x]);

         up(ma,mxdep[v[x]]);

         fa[v[x]]=u;

     }

     mxdep[u]=(ma==-N?:ma+);

 }

 void dfs_find(int u,int now)

 {

     if(fg)return;

     if(now==len){fg=;return;}

     if(mxdep[u]>len-now)

     {

         for(int i=g[u];i;i=nxt[i])

             if(str[v[i]]==S[now+]&&!vis[v[i]])

                 vis[v[i]]=,dfs_find(v[i],now+),vis[v[i]]=;

     }

     else if(str[fa[u]]==S[now+]&&!vis[fa[u]])

                 vis[fa[u]]=,dfs_find(fa[u],now+),vis[fa[u]]=;

 }

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         memset(g,,sizeof(g)),ed=;

         F(i,,n-)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             adg(x,y),adg(y,x);

         }

         scanf("%s%s",str+,S+);

         len=strlen(S+);

         memset(vis,,sizeof(vis));

         init_dfs(),fg=;

         F(i,,n)if(str[i]==S[])

         {

             memset(vis,,sizeof(vis));

             vis[i]=,dfs_find(i,);

         }

         printf("Case #%d: %s\n",++ic,fg?"Find":"Impossible");

     }

     return ;

 }