题意:

  给一棵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代码

最新文章

  1. 带你学C,带你飞——入门
  2. xUtils3的简单介绍
  3. 运行ASP程序报错
  4. Sqli-labs less 18
  5. WCF再学习小结
  6. iOS开发——Block详解
  7. MFC中cannot find the definition (implementation) of this function 解决方法
  8. 私人定制javascript中数组小知识点(Only For Me)
  9. Java中的移动和复制
  10. kubernetes dashboard backend源码剖析
  11. 关于ES6的module的循环加载
  12. 【C语音基础】printf()用法
  13. node.js服务端程序在Linux上持久运行
  14. XSS跨站脚本小结(转)
  15. java 空格替换%20
  16. umdh windbg分析内存泄露
  17. SQL 分页 SQL SERVER 2008
  18. Windows7下搭建Android开发环境
  19. 关于 initWithNibName 和 loadNibNamed 的区别和联系-iPhone成长之路
  20. MySql安装错误代码1045的解决方案

热门文章

  1. wannafly test D
  2. Java编程环境IntelliJ IDEA
  3. WordCount作业提交到FileInputFormat类中split切分算法和host选择算法过程源码分析
  4. HDOj-1425
  5. In-App Purchase Programming Guide----(一) ---- About In-App Purchase
  6. IsPostBack深入探讨
  7. eclipse neon 离线安装插件
  8. lightoj 1096【矩阵快速幂(作为以后的模板)】
  9. 在OpenCV for Android 2.4.5中使用SURF(nonfree module)
  10. 混用ngui和ugui渲染顺序问题