题意：
给一棵n节点的树图，每个点都是一个小写字母，要求找到两个点(a,b)，从a->b的路径上形成了一个字符串为s。给出s，问是否存在这样的点对。
思路：
考虑一个点，要么从该点出发，要么在该点结束，要么它作为一个中间点将左右两个串连起来成为s。叶子只能是起点或者终点。在每个点中需要保存两个队列，表示有点可以从正or反向走到这个点的长度（即前缀与后缀，但只需记录当前点是排在第几）。对于在本节点连接的情况，枚举一下哪些孩子可能在本节点连接就行了。
2s多
#include <bits/stdc++.h>
#define pii pair<int,int>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)<0?-(x):(x))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const double PI = acos(-1.0);
const int N=;
struct node
{
int from, to, next;
node(){};
node(int from,int to,int next):from(from),to(to),next(next){};
}edge[N*]; int head[N], edge_cnt, n, m;
char c[N], s[N];
void add_node(int from,int to)
{
edge[edge_cnt]=node(from,to,head[from]);
head[from]=edge_cnt++;
} bitset<> mapp[N], mapp2[N];
deque<int> que1[N], que2[N];
bool ans;
void DFS(int t,int far)
{
node e;
for(int i=head[t]; i!=- && ans==false; i=e.next)
{
e=edge[i];
if(e.to==far) continue;
DFS(e.to, t); int siz=que1[e.to].size();
for(int j=; j<siz; j++) //将que1装进来先
{
int r=que1[e.to].front();
que1[e.to].pop_front();
que1[e.to].push_back(r); //que1[e.to]并没有删除
if( c[t]==s[r+] )
{
if(mapp[t][r+]) mapp2[t][r+]=; //增加1个位表示是否有两个孩子能连到此点
else if(!mapp[t][r+]) mapp[t][r+]=,que1[t].push_back(r+);
if(r+==m)
{
ans=true;
return ;
}
}
}
} for(int i=head[t]; i!=- && ans==false; i=e.next) //考虑每个孩子
{
e=edge[i];if(e.to==far) continue; int siz=que1[e.to].size(); //先把此孩子的左，从mapp中全部去掉
for(int j=; j<siz; j++)
{
int r=que1[e.to].front();
que1[e.to].pop_front();
que1[e.to].push_back(r);
if( c[t]==s[r+] && !mapp2[t][r+] ) mapp[t][r+]=;
} siz=que2[e.to].size(); //判断是否在此点链接
for(int i=; i<siz; i++)
{
int r=que2[e.to].front();
que2[e.to].pop_front();
que2[e.to].push_back(r); //que2还没有删
if( mapp[t][r-]== ){ ans=true; return ;} //找到了另一半
} while( !que2[e.to].empty() ) //找不到时，再将que2装进去
{
int r=que2[e.to].front();que2[e.to].pop_front();
if( c[t]==s[r-] ) //刚好相同
{
que2[t].push_back( r- );
if(r-==) //以此点为终点
{
ans=true;
return ;
}
}
} while( !que1[e.to].empty() ) //将此孩子的que1装回去
{
int r=que1[e.to].front();
que1[e.to].pop_front();
if( c[t]==s[r+] )
{
if( !mapp[t][r+] ) mapp[t][r+]=;
}
}
}
if(c[t]==s[]) que1[t].push_back(); //起点或终点
if(c[t]==s[m]) que2[t].push_back(m);
} bool test() //s的长度为1的情况
{
for(int i=; i<=n; i++)
if(c[i]==s[]) return true;
return false;
} void init()
{
edge_cnt=;
ans=false;
memset(head,-,sizeof(head));
for(int i=; i<=n; i++)
mapp[i].reset(),
mapp2[i].reset(),
que1[i].clear(),
que2[i].clear();
} int main()
{
//freopen("input.txt", "r", stdin);
int t, a, b, Case=;
cin>>t;
while(t--)
{
scanf("%d",&n);
init();
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
add_node(a,b);
add_node(b,a);
}
scanf("%s", c+);
scanf("%s", s+);
m=strlen(s+); DFS(,-);
if(m==)
{
if( test() ) printf("Case #%d: Find\n", ++Case);
else printf("Case #%d: Impossible\n", ++Case);
}
else if(m<=n&&ans==true)printf("Case #%d: Find\n", ++Case);
else printf("Case #%d: Impossible\n", ++Case);
}
return ;
}
AC代码