一道不知名的题目

Trie 可持久化Trie 启发式合并 最小生成树 线段树合并

题面

有一棵大小为$n$的带边权、点权的树，问有多少点对$(i,j)(i<j)$满足：
点权异或和$>$树上简单路径的最大边权。

• $n\leq2*10^5$

解析

这个最大边权显然不是暴力求出来的，因为要求给出两个点，复杂度$O(n^2)$。
所以我们要枚举边权。

一开始可能会想到，从最大边开始，统计其两端子树之间的贡献，然后分治搞下去。
但这样其实很难保证复杂度。
换个方向思考，可以像做最小生成树一样，从小往大加边。
显然每加一条边，这条边就是两端联通块相互之间的最大边权。

然后异或和显然可以弄棵$Trie$树来搞。
这个$Tire$树可以跟着并查集一起维护，每次合并并查集的同时把$Trie$树也合并。
所以需要线段树合并$or$可持久化$Trie$。
（注意如果一个一个点地合并$Trie$树会$TLE$!!!)

最后注意边界，$Insert$到$d<0$时，新建结点再$return$；而$Query$直接$return$。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e5+100;
int n,val[N],W,h[N],cnt,sz[N*32],da[N],t[2][N*32],f[N],rt[N],sta[N*32],top;
ll ans;
struct dat{int u,v,w;il bool operator < (const dat &o) const {return w<o.w;}}a[N];
struct Edge{int to,nxt;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Insert(re int &x,re int k,re int d)
{
  if(!x) x=sta[top--];++sz[x];
  if(d<0) return;
  Insert(t[(k>>d)&1][x],k,d-1);
}
il int Query(re int x,re int k,re int w,re int d)
{
  if(d<0) return 0;
  re int A=k>>d&1,B=w>>d&1,s=0;
  if(!B) s+=sz[t[A^1][x]];
  s+=Query(t[A^B][x],k,w,d-1);
  return s;
}
il void dfs1(re int u,re int fa,re int x,re int w)
{
  ans+=Query(rt[x],val[u],w,29);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u,x,w);
    }
}
il void clear(re int x)
{
  if(!x) return;
  clear(t[0][x]);clear(t[1][x]);
  t[0][x]=t[1][x]=sz[x]=0;sta[++top]=x;
}
il int Merge(re int x,re int y)
{
  if(x) sz[x]+=sz[y];
  if(!x||!y) return x+y;
  t[0][x]=Merge(t[0][x],t[0][y]);
  t[1][x]=Merge(t[1][x],t[1][y]);
  return x;
}
int main()
{
  memset(h,-1,sizeof(h));
  fq(i,2e5*32,1) sta[++top]=i;
  n=gi();
  fp(i,1,n) val[i]=gi(),f[i]=i,da[i]=1,Insert(rt[i],val[i],29);
  fp(i,1,n-1) a[i].u=gi(),a[i].v=gi(),a[i].w=gi();
  sort(a+1,a+n);
  fp(i,1,n-1)
    {
      re int u=find(a[i].u),v=find(a[i].v);
      if(da[u]<da[v]) swap(u,v);
      dfs1(v,0,u,a[i].w);Merge(rt[u],rt[v]);
      f[v]=u;da[u]+=da[v];add(u,v);
    }
  printf("%lld\n",ans);
  return 0;
}