[关闭]
@ysner 2018-08-03T17:15:13.000000Z 字数 2039 阅读 1639

[TJOI2018]异或

可持久化Trie 树链剖分


题面

有一棵带点权的大小为的树。有次操作:

解析

这似乎是可持久化树模板和链剖模板二合一。
用链剖像维护线段树一般维护树即可。
然后因sum空间开小调了一个小时

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