给定一棵树，每条边有一个权值，定义f(u,v)为树链(u,v)的异或和。Q次询问[l,r]中f(u,v)>M的个数。
对于一棵树，有f(u,v)=f(1,u)^f(1,v),然后就转化为一个序列上的问题。
答案用字典树维护。将每个数按数位从高到低插入字典树中（含前缀0）。对于询问就从字典树上往下走，（设这个数为x）每次走x当前位跟m当前位的异或值，如果m的当前位为0，就加上另一个节点的size。
不知道错哪了。欢迎来指正。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define sqr(x) ((x)*(x))
#define G getchar()
#define LL long long
#define pll pair<LL,LL>
#define mkp make_pair
#define X first
#define Y second
#define N 100005
#define NN 1600005
struct QUERY{int L,R,wz;}qu[N];int n,m,Q,numm[20];
int tot,he[N],ne[N<<1],to[N<<1],W[N<<1];
int a[N],mo[N],s,t;LL now,ans[N];
int c[2][NN],stk[NN],Tp,mTp;LL cnt[NN];
int read(){
int x=0;char ch=G;
for(;ch<48||ch>57;ch=G);
for(;ch>47&&ch<58;ch=G)x=x*10+ch-48;
return x;
}
void add(int x,int y,int z){
to[++tot]=y;ne[tot]=he[x];W[tot]=z;he[x]=tot;
}
void DFS(int x,int e){
int i,y;
for(i=he[x];i;i=ne[i])if(i!=e){
a[y=to[i]]=a[x]^W[i];DFS(y,i^1);
}
}
bool cmp(QUERY x,QUERY y){
return mo[x.L]==mo[y.L]?x.R<y.R:mo[x.L]<mo[y.L];
}
int get(){
int rtn=stk[Tp++];mTp=max(mTp,Tp);
c[0][rtn]=c[1][rtn]=cnt[rtn]=0;
return rtn;
}
void ins(int x){
int i,num[20];
rep(i,0,19){num[i]=x&1;x>>=1;}x=1;
per(i,19,0){
int &y=c[num[i]][x];
if(!y){y=get();c[0][y]=c[1][y]=0;}
++cnt[x=y];
}
}
void del(int x){
int i,num[20],y;
rep(i,0,19){num[i]=x&1;x>>=1;}x=1;
per(i,19,0){
int &y=c[num[i]][x];x=y;
if(--cnt[y]==0){stk[--Tp]=y;y=0;}
}
}
int cal(int x){
int i,num[20],rtn=0;
rep(i,0,19){num[i]=x&1;x>>=1;}x=1;
per(i,19,0){
if(!x)break;
if(numm[i])x=c[!num[i]][x];
else{rtn+=cnt[c[!num[i]][x]];x=c[num[i]][x];}
}
return rtn;
}
int main(){
freopen("r.in","r",stdin);
freopen("w.out","w",stdout);
int i,x,y,z,l,r;
per(i,NN-1,0)stk[i]=i;
while(~scanf("%d%d%d",&n,&m,&Q)){
s=ceil(sqrt(n));
rep(i,1,n)he[i]=0,mo[i]=t+=i%s==1;
tot=1;
rep(i,2,n){
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
DFS(1,0);
rep(i,1,Q){
x=read();y=read();qu[i]=(QUERY){x,y,i};
}
sort(qu+1,qu+Q+1,cmp);
per(i,mTp-1,2)stk[i]=i;mTp=Tp=2;c[0][1]=c[1][1]=0;
ins(a[l=r=qu[1].L]);now=0;
rep(i,0,19){numm[i]=m&1;m>>=1;}
rep(i,1,n){
while(r<qu[i].R){ins(a[++r]);now+=cal(a[r]);}
while(r>qu[i].R){now-=cal(a[r]);del(a[r--]);}
while(l>qu[i].L){ins(a[--l]);now+=cal(a[l]);}
while(l<qu[i].L){now-=cal(a[l]);del(a[l++]);}
ans[qu[i].wz]=now;
}
rep(i,1,Q)printf("%lld\n",ans[i]);
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-51253.html
