https://www.zybuluo.com/ysner/note/1311166
题面
有一棵大小为(n)的带边权、点权的树，问有多少点对((i,j)(i<j))满足：
点权异或和(>)树上简单路径的最大边权。
- (nleq2*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
",ans);
return 0;
}