题目链接
思路:
题意人问你在第一棵树中能找到多少和第二颗树完全相同的？
这个题当时我有想法，就是感觉不好实现...是我想复杂了 orz..
我们在数据结构中可以知道,先序遍历和后序遍历可以确定一棵树(应该是吧。。。)那么对于这个题我们就对两个树进行一次遍历转化成一行,然后进行KMP就能得到可以匹配几次。我们又可以看出序列一样的匹配出来的并不一定完全相同,那是因为没有排除叶子的情况,所以我们对于一棵树的叶子节点用一个题目中不会出现的来表示,其余的用权值来表示,这样就可以保证匹配到的一定是正确的了。
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; vector<int>va[maxn],vb[maxn]; int n,m; string s1,s2; int cnt1[maxn],cnt2[maxn]; int w1[maxn],w2[maxn]; int nextt[maxn]; ll ans=0; void dfs1(int v) { if(!v) { s1+='a'; return ; } else { s1+=(w1[v]+'a'); for(int i=0;i<va[v].size();i++) { dfs1(va[v][i]); } } return ; } void dfs2(int v) { if(!v) { s2+='a'; return ; } else { s2+=(w2[v]+'a'); for(int i=0;i<vb[v].size();i++) { dfs2(vb[v][i]); } } return ; } void get_next() { nextt[0]=-1; int i=0,j=-1; while(i<s2.size()) { if(j==-1||s2[i]==s2[j]) nextt[++i]=++j; else j=nextt[j]; } return ; } void KMP() { int i=0,j=0; while(i<s1.size()) { if(j==-1||s1[i]==s2[j]) { if(j==s2.size()-1) { ans++; j=nextt[j]; } else { i++,j++; } } else j=nextt[j]; } return ; } int main() { while(~Ri(n)) { CLR(cnt1,0); CLR(cnt2,0); Ri(m); s1=""; s2=""; int w,l,r; for(int i=1;i<=n;i++) { va[i].clear(); Ri(w1[i]),Ri(l),Ri(r); va[i].pb(l); va[i].pb(r); cnt1[l]++; cnt1[r]++; } int r1=0,r2=0; for(int i=1;i<=n;i++) { if(cnt1[i]==0) { r1=i; break; } } for(int i=1;i<=m;i++) { vb[i].clear(); Ri(w2[i]),Ri(l),Ri(r); vb[i].pb(l); vb[i].pb(r); cnt2[l]++; cnt2[r]++; } for(int i=1;i<=m;i++) { if(cnt2[i]==0) { r2=i; break; } } //cout<<cnt2[3]<<endl; //cout<<r1<<endl; //cout<<r2<<endl; dfs1(r1); dfs2(r2); get_next(); ans=0; KMP(); //cout<<s1<<endl; //cout<<s2<<endl; Pl(ans); } return 0; } /*************************************************** User name: ironman Result: Accepted Take time: 2404ms Take Memory: 6148KB Submit time: 2017-06-06 15:40:24 ****************************************************/ Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
