[关闭]
@ysner 2018-09-29T16:48:06.000000Z 字数 2114 阅读 1803

[Jsoi2015]字符串树

树链剖分 可持久化Tire树 Tire


题面

字符串树本质上还是一棵树,即个节点条边的连通无向无环图,节点
编号。与普通的树不同的是,树上的每条边都对应了一个字符串。萌萌
在树下玩的时候,萌萌决定考一考。每次萌萌都写出一个字符串
两个节点,需要立即回答之间的最短路径(即之间边数最少的
路径。由于给定的是一棵树,这样的路径是唯一的)上有多少个字符串以为前
缀。

解析

维护树上距离,我能想到的也只有树链剖分了。
树链剖分维护树上距离,实际上是通过每个点到根节点的距离来进行的。

那么这题也一样。
维护一下每个点到根节点的字符串。
又因为求的是前缀,可以用树维护。
注意到各节点字符串是有重复的。为了节省空间,可以把树可持久化。
然后就完事了。

其实我一开始做这题时不知道怎么把字符串作为边权。。。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define ls x<<1
  12. #define rs x<<1|1
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int N=1e5+100;
  17. int n,q,h[N],cnt,sz[N],son[N],f[N],top[N],d[N],rt[N*100],tot;
  18. struct Tire{int son[26],w;}t[N*60];
  19. struct Edge{int to,nxt;char *s;}e[N<<1];
  20. il void add(re int u,re int v,re char *s){e[++cnt]=(Edge){v,h[u],s};h[u]=cnt;}
  21. char op[N][15];
  22. il ll gi()
  23. {
  24. re ll x=0,t=1;
  25. re char ch=getchar();
  26. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  27. if(ch=='-') t=-1,ch=getchar();
  28. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  29. return x*t;
  30. }
  31. il void Insert(re int &u,re char *s,re int x,re int n)
  32. {
  33. t[++tot]=t[u];u=tot;++t[u].w;
  34. if(x>n) return;
  35. Insert(t[u].son[s[x]-'a'],s,x+1,n);
  36. }
  37. il ll Query(re int u,re char *s,re int n)
  38. {
  39. fp(i,1,n) u=t[u].son[s[i]-'a'];
  40. return t[u].w;
  41. }
  42. il void dfs1(re int u,re int fa)
  43. {
  44. f[u]=fa;sz[u]=1;d[u]=d[fa]+1;
  45. for(re int i=h[u];i+1;i=e[i].nxt)
  46. {
  47. re int v=e[i].to;
  48. if(v==fa) continue;
  49. Insert(rt[v]=rt[u],e[i].s,1,strlen(e[i].s+1));
  50. dfs1(v,u);
  51. sz[u]+=sz[v];
  52. if(sz[v]>sz[son[u]]) son[u]=v;
  53. }
  54. }
  55. il void dfs2(re int u,re int up)
  56. {
  57. top[u]=up;
  58. if(son[u]) dfs2(son[u],up);
  59. for(re int i=h[u];i+1;i=e[i].nxt)
  60. {
  61. re int v=e[i].to;
  62. if(v==f[u]||v==son[u]) continue;
  63. dfs2(v,v);
  64. }
  65. }
  66. il int getLCA(re int u,re int v)
  67. {
  68. while(top[u]^top[v])
  69. {
  70. if(d[top[u]]<d[top[v]]) swap(u,v);
  71. u=f[top[u]];
  72. }
  73. return d[u]<d[v]?u:v;
  74. }
  75. int main()
  76. {
  77. memset(h,-1,sizeof(h));
  78. n=gi();
  79. fp(i,1,n-1)
  80. {
  81. re int u=gi(),v=gi();scanf("%s",op[i]+1);
  82. add(u,v,op[i]);add(v,u,op[i]);
  83. }
  84. dfs1(1,0);dfs2(1,1);
  85. q=gi();
  86. while(q--)
  87. {
  88. re int u=gi(),v=gi(),lca=getLCA(u,v);scanf("%s",op[0]+1);
  89. re int len=strlen(op[0]+1);
  90. printf("%lld\n",Query(rt[u],op[0],len)+Query(rt[v],op[0],len)-2*Query(rt[lca],op[0],len));
  91. }
  92. return 0;
  93. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注