本文共 1502 字，大约阅读时间需要 5 分钟。
给定一棵 n 个点的树，树上每个节点代表一个小写字母，询问一个字符串 S 是否在树上出现过？ 字符串 S 出现过即表示存在两个点 u,v，u 到 v 的最短路径上依次连接所有点上的字母恰好是 S
N ≤ 10^4
直接寻找即可，注意特殊情况，加一个小优化优化非常多。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define il inline13 #define re register14 using namespace std;15 const int N=20001;16 struct edge{ int next,to;17 } e[N];18 int T,n,g[N][26],M,m,d[N],x[N],y[N],exist[101];19 bool flag;20 char p[N],q[N];21 il void addedge(re int x,re int y){22 e[++M]=(edge){g[x][p[y]-'a'],y};g[x][p[y]-'a']=M;23 }24 il bool dfs(re int h,re int fa,re int d){25 //printf("%d %d %d\n",h,fa,d);26 if(d==m){27 return true;28 }29 for(re int i=g[h][q[d+1]-'a'],k;i;i=e[i].next){30 k=e[i].to;31 if(k==fa) continue;32 if(dfs(k,h,d+1)) return true;33 }34 return false;35 }36 il bool dfs1(re int h,re int fa){37 for(int j=0;j<26;j++){38 for(int i=g[h][j];i;i=e[i].next){39 if(e[i].to==fa) continue;40 d[e[i].to]=d[h]+1;41 dfs1(e[i].to,h);42 }43 }44 }45 int main(){46 freopen("alphabet.in","r",stdin);47 freopen("alphabet.out","w",stdout);48 scanf("%d",&T);49 for(int it=1;it<=T;it++){50 memset(g,false,sizeof(g));51 memset(exist,false,sizeof(exist));52 scanf("%d",&n);M=0;flag=true;53 for(int i=1;i d[sp]) sp=i;78 d[sp]=1;dfs1(sp,0);79 for(int i=1;i<=n;i++)80 if(d[i]>d[sp]) sp=i;81 if(d[sp]
转载于:https://www.cnblogs.com/ExiledPoet/p/5771106.html